يک الگوريتم جديد مبتني بر آتاماتاي يادگير توزيع‌شده توسعه‌يافته براي يادگيري پارامتري شبکه بيزي
محورهای موضوعی : مهندسی برق و کامپیوترمحمدرضا ملاخلیلی میبدی 1 * , محمدرضا میبدی 2
1 - دانشگاه آزاد اسلامی، واحد میبد
2 - دانشگاه صنعتی امیرکبیر
کلید واژه: آتاماتاي يادگير شبکه بيزي يادگيري پارامتري,
چکیده مقاله :
در اين مقاله يک آتاماتاي توزيع‌شده جديد به نام آتاماتاي يادگير توزيع‌شده توسعه‌يافته براي يادگيري توزيع توأم مجموعه‌اي از متغيرهاي تصادفي معرفي خواهد شد. اين شبکه از آتاماتاها در محيط‌هايي که پاسخ محيط به مجموعه‌اي از اقدامات انجام‌شده توسط آتاماتا، مستقل از يکديگر نبوده و نوعي وابستگي شرطي ميان اين پاسخ‌ها حاکم باشد، کاربرد دارد. نشان داده شده که اين آتاماتاي جديد قادر است تخميني از توزيع شرطي اقدام‌ها را فرا بگيرد. در ادامه چارچوبی مبتني بر آتاماتاي يادگير توزيع‌شده جديد پيشنهادي، براي حل مسأله يادگيري برخط پارامترهاي یک شبکه بیزی ارائه شده است. اين چارچوب با داده‌ها و شواهد جديد منطبق شده و عمليات به روز رساني پارامترها را انجام مي‌دهد. با بررسي‌هاي رياضي و آزمايش‌هاي عملي روي شبکه‌هاي نمونه، نشان داده‌ايم که اين مدل جديد قادر است با تخميني با دقت برابر با EM، يادگيري پارامترهاي يک شبکه بيزي را انجام دهد. علاوه بر ويژگي افتراقی‌بودن و يادگيري برخط، اين ساختار جديد با شرايطي که داده‌ها ناکامل باشند نيز سازگار است و به دليل استفاده از روابط يادگيري خطي و مبتني بر آتاماتاي يادگير، سربار محاسباتي کمي نيز دارد.
In this paper a new learning automata-based algorithm is proposed for learning of parameters of a Bayesian network. For this purpose, a new team of learning automata which is called eDLA is used. In this paper the structure of Bayesian network is assumed to be fixed. New arriving sample plays role of the random environment and the accuracy of the current parameters generates the random environment reinforcement signal. Linear algorithm is used to update the action selection probability of the automata. Another key issue in Bayesian networks is parameter learning under circumstances that new samples are incomplete. It is shown that new proposed method can be used in this situation. The experiments show that the accuracy of the proposed automata based algorithm is the same as the traditional enumerative methods such as EM. In addition to the online learning characteristics, the proposed algorithm is in accordance with the conditions in which the data are incomplete and due to the use of learning automaton, has a little computational overhead.
[1] F. V. Jensen and T. D. Nielsen, Bayesian Networks and Decision Graphs, Springer, 2007.
[2] 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.
[3] M. L. Thathachar and P. S. Sastry, "Varieties of learning automata: an overview," IEEE Trans. Syst. Man. Cybern. B. Cybern., vol. 32, no. 6, pp. 711-722, Jan. 2002.
[4] K. S. Narendra and M. A. L. Thathachar, "Larning automata: a survey," IEEE Trans. Syst. Man, Cybern. - Part A Syst. Humans, vol. 14, no. 4, pp. 323-334, Jul. 1974.
[5] H. Beigy and M. Meybodi, Intelligent Channel Assignment in Cellular Networks: A Learning Automata Approach, Amirkabir University of Technology, 2004.
[6] A. S. Poznyak and K. Najim, Learning Automata and Stochastic Optimization (Lecture Notes in Control and Information Sciences), vol. 225, London: Springer - Verlag, 1997.
[7] 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.
[8] M. R. Mollakhalili Meybodi and M. R. Meybodi, "A new distributed learning automata based algorithm for solving stochastic shortest path," in Proc. 6th Conf. on Intelligent Systems, Nov. 26-27, 2004.
[9] M. R. Meybodi and H. Beigy, "A sampling method based on distributed learning automata," in Proc. 10th Iranian Conf. on Electrical Engineering, vol. 1, pp. 618-626, May 2002.
[10] A. Motevalian and M. R. Meybodi, "Solving maximal independent set problem using distributed learning automata," in Proc.14th Iranian Electrical Engineering Conf., ICEE 2006, vol. 1, Tehran, Iran, 16-18 May 2006.
[11] A. Alipour and M. R. Meybodi, "Solving traveling salesman problem using distributed learning automata," in Proc. 10th Annual CSI Computer Conf., pp. 759-761, Tehran, Iran, Feb. 2005.
[12] A. Baradaran Hashemi and M. R. Meybodi, "Web usage mining using distributed learning automata," in Proc. 12th Annual CSI Computer Conf. of Iran, pp. 553-560, Tehran, Iran, 20-22 Feb. 2007.
[13] M. R. Mollakhalili Meybodi and M. R. Meybodi, "A distributed learning automata based approach for user modeling in adaptive hypermedia," in Proc. Congress on Electrical, Computer, and Information Technology, Mashhad, Iran, 7-9 Nov. 2012.
[14] M. R. Mollakhalili Meybodi and M. R. Meybodi, "Link prediction in adaptive web sites using distributed learning automata," in Proc. 13th Annual CSI Computer Conf. of Iran, 6 pp., Kish Island, Iran, March 9-11, 2008.
[15] B. Anari and M. R. Meybodi, "A method based on distributed learning automata for determining web documents structure," in proc. 12th Annual CSI Computer Conf. of Iran, pp. 2276-2282, 20-22 Feb.. 2007.
[16] E. Bauer, D. Koller, and Y. Singer, "Update rules for parameter estimation in bayesian networks," in Proc. of the 13th Conf. on Uncertainty in Artificial Intelligence, UAI1997, pp. 3-13, 1997.
[17] I. Cohen, A. Bronstein, F. G. Cozman, and N. M. A. Urbana, Online Learning of Bayesian Network Parameters, Technical Report, 2001.
[18] N. A. Rezvani and M. R. Meybodi, "A learning automata - based technique for training conditional probability tables of bayesian network," in Proc. 14th National Conf. of Iran Computer Society, CSICC'09, Tehran, Iran, 2009.
[19] M. R. Mollakhalili Meybodi and M. R. Meybodi, "Extended distributed learning automata: a new method for solving stochastic graph optimization problems," vol. 41, no. 3, pp. 923-940, Aug. 2013.
[20] P. Murphy Kevin, An Introduction to Graphical Models, 2001.
[21] C. B. G., G. Suermondt, and R. Chavez, "The ALARM monitoring system: a case study with two probabilistic inference techniques for belief networks," in Proc. 2nd European Conf. on AI and Medicine, vol. 38, pp. 247-256, 1989.
[22] "Bayesian network repository," [Online]. Available: http://www.cs.huji.ac.il/~galel/Repository.