Leaning the Structure of Bayesian Networks Using Learning Automata
Subject Areas : electrical and computer engineeringM. R. Mollakhalili Meybodi 1 * , M. R. Meybodi 2
1 -
2 -
Keywords: Learning automata Bayesian network structure learning,
Abstract :
The structure of a Bayesian network represents a set of conditional independence relations that hold in the domain. Learning the structure of the Bayesian network model that represents a domain can reveal in sights into its underlying causal structure. Automatically learning the graph structure of a Bayesian network is a challenge pursued within artificial intelligence studies. In this paper, a new algorithm based on learning automata is proposed for learning the structure of the Bayesian networks. In this algorithm, automata is used as a tool for searching in structure’s space (DAG’s space) of the Bayesian networks. The mathematical behavior of the proposed algorithm is studied.
[1] L. de Campos and J. Puerta, "Stochastic local algorithms for learning belief networks: searching in the space of the orderings," in Symbolic and Quantitative Approaches to Reasoning with Uncertainty, vol. 2143, pp. 228-239, 2001.
[2] D. Heckerman, A Tutorial on Learning with Bayesian Networks, in Innovations in Bayesian Networks, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 33-82,1996.
[3] T. Nielsen and F. Jensen, Bayesian Networks and Decision Graphs, 2nd Ed. Springer, 2009.
[4] D. M. Chickering, "Learning Bayesian networks is NP-complete," in Learning from Data, Springer, pp. 121-130, 1996.
[5] W. Buntine, "A guide to the literature on learning probabilistic networks from data," IEEE Trans. Knowl. Data Eng., vol. 8, no. 2, pp. 195-210, Apr. 1996.
[6] G. F. Cooper and E. Herskovits, "A Bayesian method for the induction of probabilistic networks from data," Mach. Learn., vol. 9, no. 4, pp. 309-347, 1992.
[7] D. Heckerman and D. M. Chickering, "Learning Bayesian networks: the combination of knowledge and statistical data metrics for belief networks," Mach. Learn., vol. 20, no. 3, pp. 197-243, 1995.
[8] W. Lam and F. Bacchus, "Learning Bayesian belief networks: an approach based on the MDL principle," Comput. Intell., vol. 10, no. 3, pp. 269-293, Aug. 1994.
[9] L. De Campos and J. Fernandez-Luna, "Ant colony optimization for learning Bayesian networks," Int. J. Approx. Reason., vol. 31, no. 3, pp. 291-311, 2002.
[10] D. Chickering, D. Geiger, and D. Heckerman, "Learning Bayesian networks: search methods and experimental results," in Proc. 5th Conf. Artif. Intell. Stat., pp. 112-128, 1995.
[11] ف. مریخبیات، الگوریتمهای بهینهسازی الهامگرفته از طبیعت، نص، 1391.
[12] K. Shibata, H. Nakano, and A. Miyauchi, "A learning method for dynamic Bayesian network structures using a multi-objective particle swarm optimizer," Artif. Life Robot., vol. 16, no. 3, pp. 329-332, Dec. 2011.
[13] K. Salama and A. Freitas, "ABC-miner: an ant-based Bayesian classification algorithm," Swarm Intell., 2012.
[14] T. Wang and J. Yang, "A heuristic method for learning Bayesian networks using discrete particle swarm optimization," Knowl. Inf. Syst., vol. 24, no. 2, pp. 269-281, Aug. 2009.
[15] P. C. Pinto, A. Nagele, M. Dejori, T. A. Runkler, and J. M. C. Sousa, "Using a local discovery ant algorithm for Bayesian network structure learning," IEEE Trans. Evol. Comput., vol. 13, no. 4, pp. 767-779, Aug. 2009.
[16] R. Daly, Q. Shen, and S. Aitken, "Using ant colony optimization in learning Bayesian network equivalence classes," in Proc. UKCI, pp. 111-118, 2006.
[17] T. Brouard, A. Delaplace, and H. Cardot, Evolutionary Methods for Learning Bayesian Network Structures, 2008.
[18] J. Lee, W. Chung, E. Kim, and S. Kim, "A new genetic approach for structure learning of Bayesian networks: matrix genetic algorithm," Int. J. Control. Autom. Syst., vol. 8, no. 2, pp. 398-407, Apr. 2010.
[19] L. de Campos and J. Huete, "On the use of independence relationships for learning simplified belief networks," Int. J. Intell. Syst., vol. 12, no. 7, pp. 495-522, 1997.
[20] S. Acid and L. M. de Campos, "A hybrid methodology for learning belief networks: BENEDICT," Int. J. Approx. Reason., vol. 27, no. 3, pp. 235-262, Sep. 2001.
[21] R. Blanco, I. Inza, and P. Larranaga, "Learning Bayesian networks in the space of structures by estimation of distribution algorithms," Int. J. Intell. Syst., vol. 18, no. 2, pp. 205-220, Feb. 2003.
[22] M. Teyssier and D. Koller, "Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks," arXiv:1207.1429, 2012.
[23] W. Hsu, H. Guo, B. Perry, and J. Stilson, "A Permutation Genetic Algorithm for Variable Ordering in Learning Bayesian Networks from Data," GECCO, 2002.
[24] P. Larranaga, C. M. H. Kuijpers, R. H. Murga, and Y. Yurramendi, "Learning Bayesian network structures by searching for the best ordering with genetic algorithms," IEEE Trans. Syst. Man, Cybern.-Part A Syst. Humans, vol. 26, no. 4, pp. 487-493, Jul. 1996.
[25] N. Friedman, M. Linial, I. Nachman, and D. Pe'er, "Using Bayesian networks to analyze expression data," J. Comput. Biol., vol. 7, no. 3-4, pp. 601-620, Jan. 2000.
[26] T. Silander and P. Myllymaki, A Simple Approach for Finding the Globally Optimal Bayesian Network Structure," arXiv Prepr. arXiv1206.6875, Jun, 2012.
[27] O. Francois, BNT Structure Learning Package: Documentation and Experiments, 2004.
[28] D. Margaritis, Learning Bayesian Network Model Structure from Data, Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, 2003.
[29] K. P. Murphy, Machine Learning: A Probabilistic Perspective (Adaptive Computation and Machine Learning Series), the MIT Press, 2012.
[30] P. Munteanu and M. Bendou, "The EQ framework for learning equivalence classes of Bayesian networks," in Proc. 2001 IEEE Int. Conf. on Data Mining, ICDM'01, pp. 417-424, San Jose, CA, USA, 2001.
[31] D. Chickering, "Learning equivalence classes of Bayesian-network structures," J. Mach. Learn. Res., vol. 2, no. 3, pp. 445-498, 2002.
[32] R. Castelo and T. Kocka, "On inclusion-driven learning of Bayesian networks," J. Mach. Learn. Res., vol. 4, pp. 527-574, 2003.
[33] D. M. Chickering, "Optimal structure identification with greedy search," J. Mach. Learn. Res., vol. 3, pp. 507-554, 2003.
[34] M. A. Thathachar and B. Harita, "Learning automata with changing number of actions," IEEE Trans. Syst. Man, Cybern.-Part A Syst. Humans, vol. 17, no. 6, pp. 1095-1100, Nov./Dec. 1987.
[35] م. ملاخلیلیمیبدی و م. میبدی، "یک الگوریتم جدید مبتنی بر آتاماتای یادگیر توزیعشده توسعهیافته برای یادگیری پارامتری شبکه بیزی،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، دوره 12، شماره 2، صص. 126-119، زمستان 1393.
[36] M. R. Mollakhalili Meybodi and M. R. Meybodi, Extended Distributed Learning Automata: A New Method for Solving Stochastic Graph Optimization Problems, arXiv Prepr. arXiv1308.2772, Aug. 2013.
[37] M. R. Mollakhalili Meybodi and M. R. Meybodi, "Extended distributed learning automata: an automata-based framework for solving stochastic graph optimization problems," Appl. Intell., vol. 41, no. 2, pp. 923-940, 2014.
[38] M. R. Mollakhalili Meybodi and M. R. Meybodi, "Solving stochastic permutation optimization using monte carlo sampling: a learning automata based framework," Submitt. to Appl. Soft Comput., 2013.
[39] م. ملاخلیلیمیبدی و م. میبدی، حل مسأله درخت پوشای کمینه تصادفی از طریق بهینهسازی جایگشت: یک رهیافت مبتنی بر آتاماتای یادگیر توزیعشده، 1395.
[40] A. Rezvanian and M. R. Meybodi, "A new learning automata-based sampling algorithm for social networks," Int. J. Commun. Syst., p. n/a–n/a, 2015.
[41] م. ملاخلیلیمیبدی و م. میبدی، "یک چارچوب مبتنی بر آتاماتای یادگیر توزیعشده توسعهیافته برای حل مسأله یافتن زیرگراف بهینه تصادفی،" نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، دوره 12، شماره 2، صص. 97-85، زمستان 1393.
[42] M. Thathachar and K. Ramakrishnan, "A hierarchical system of learning automata," IEEE Trans. Syst. Man. Cybern., vol. 11, no. 3, pp. 236-241, 1981.
[43] H. Beigy and M. R. Meybodi, "Utilizing distributed learning automata to solve stochastic shortest path problems," Int. J. Uncertainty, Fuzziness Knowledge-Based Syst., vol. 14, no. 5, pp. 591-615, Oct. 2006.
[44] F. Norman, "On the linear model with two absorbing," J. Math. Psychol., vol. 5, pp. 225-241, 1968.
[45] S. Lakshmivarahan and M. Thathachar, "Bounds on the convergence probabilities of learning automata," IEEE Trans. Syst. Man, Cybern.-Part A Syst. Humans, vol. 6, no. 11, pp. 756-763, 1976.
[46] V. Lepar and P. P. Shenoy, "A comparison of lauritzen-spiegelhalter, hugin, and shenoy-shafer architectures for computing marginals of probability distributions," in Proc. of the 14th Conf. on Uncertainty in Artificial Intelligence, UAI'98, pp. 328-337, 1998.
[47] R. M. C. G. F. C. Ingo A. Beinlich Henri Jacques Suermondt, "The ALARM Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks," 1989.