یادگیری ساختاری شبکه‌های بیزی یک رهیافت مبتنی بر آتاماتاهای یادگیر
محورهای موضوعی : مهندسی برق و کامپیوترمحمدرضا ملاخلیلی میبدی 1 * , محمدرضا میبدی 2
1 - دانشگاه آزاد اسلامی، واحد میبد
2 - دانشگاه صنعتی امیرکبیر
کلید واژه: یادگیری ساختار شبکه بیزی آتاماتای یادگیر,
چکیده مقاله :
یکی از مسایل جالب در هوش مصنوعی ساخت شبکه بیزی بر اساس نمونه‌هایی از داده‌ها است؛ یعنی فرض کنید یک شبکه بیزی N روی مجموعه متغیرهای V مفروض است. هدف، ساخت یک شبکه بیزی- استخراج مجموعه‌ای از روابط علت/ معلولی- میان مجموعه متغیرها بر اساس نمونه‌هایی که از N استخراج شده و بدون در اختیار داشتن N است. از این مسأله در متون با عنوان یادگیری ساختاری شبکه بیزی یاد می‌شود. یکی از روش‌های مهم در یادگیری ساختاری شبکه‌های بیزی با استفاده از داده‌های نمونه، استفاده از معیارهای مبتنی بر امتیاز برای ارزیابی میزان برازندگی یک ساختار بیزی مفروض با داده‌های نمونه و جست و جو در میان ساختارهای ممکن است. جست و جو برای یافتن یک ساختار مناسب برای شبکه بیزی که بیشترین سازگاری را با نمونه‌ها داشته باشد غالباً از طریق جست و جو در فضای ساختارها با استفاده از تکنیک‌های جست و جوی استاندارد یا الهام‌گرفته از طبیعت نظیر تپه‌نوردی حریصانه، الگوریتم‌های ژنتیک، شبیه‌سازی حرارتی یا الگوریتم تبرید، بهینه‌سازی کلونی مورچه‌ها و نظایر آن صورت می‌گیرد. در این مقاله یک روش جدید مبتنی بر آتاماتای یادگیر برای یادگیری ساختاری شبکه بیزی ارائه شده است. در این روش آتاماتای یادگیر به عنوان یک ابزار جستجوی تصادفی مورد استفاده قرار می‌گیرد. از ویژگی‌های روش جدید پیشنهادی جستجوی هم‌زمان در فضای جایگشت‌های ممکن از متغیرها (فضای ترتیب متغیرها) و فضای ساختارها (فضای DAGها) است. ضمن بررسی ریاضی الگوریتم پیشنهادی، روش جدید روی تعدادی از شبکه‌های نمونه مورد آزمایش قرار گرفته است.
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.