یادگیری ساختار شبکه‌های بیزین با استفاده از روش گردکردن قطعی

نویسندگان
شهاب بهجتی 1
حمید بیگی 2
1 دانش آموخته دکتری، علوم کامپیوتر، پژوهشکده علوم کامپیوتر، پژوهشگاه دانشهای بنیادی، تهران، ایران
2 دانشیار، مهندسی کامپیوتر، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی شریف، تهران، ایران
چکیده
شبکه‌های بیزین یکی از پرکاربردترین مدل‌های گرافی احتمالاتی بوده که برای نمایش یک توزیع احتمال به کار رفته و دارای کاربردهای بسیار متنوع در هوش مصنوعی، داده کاوی و یادگیری ماشین است. یکی از مهم‌ترین مسائل در این شبکه‌ها، مسئله‌ یادگیری ساختار از روی مجموعه داده‌ها آموزشی است. به طور کلی روش‌های یادگیری ساختار به سه دسته مبتنی بر محدودیت، مبتنی بر امتیاز و ترکیبی تقسیم می‌شوند. در این مقاله یک روش مبتنی بر امتیاز جهت ساخت شبکه بیزین ارائه می‌شود که مبتنی بر روش گردسازی قطعی در برنامه‌ریزی خطی است.روش پیشنهادی ابتدا مسئله یادگیری ساختار را به صورت یک برنامه خطی صحیح مدل‌سازی نموده و سپس آن را به یک مسئله برنامه ریزی خطی تعدیل می‌کند. سپس با حل برنامه خطی تعدیل شده، جواب‌های کسری به دست آمده را با استفاده از روش معرفی شده گردسازی قطعی به جواب‌های صحیح تبدیل می‌کند.

کلیدواژه‌ها

  • [1] D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
  • [2] B. Moradabadi and H. Beigy, “A new real-coded bayesian optimization algorithm based on a team of learning automata for continuous optimization,” Genetic programming and evolvable machines, vol.15, no.2, pp.169–193, 2014.
  • [3] Z.-b. Zhou, D. D. DONG, J. L. Zhou, “Application of bayesian networks in reliability analysis,” Systems Engineering-Theory & Practice, vol.6, pp.95–100, 2006.
  • [4] J. Zhu and A. Deshmukh, “Application of Bayesian decision networks to life cycle engineering in green design and manufacturing,” Engineering Applications of Artificial Intelligence, vol.16, no.2, pp.91–103, 2003.
  • [5] B. Malekmohammadi, R. Kerachian, and B. Zahraie, “Developing monthly operating rules for a cascade system of reservoirs: application of bayesian networks,” Environmental Modelling & Software, vol.24, no.12, pp.1420–1432, 2009.
  • [6] W. A. Wiest, M. D. Correll, B. G. Marcot, B. J. Olsen, C. S. Elphick, T. P. Hodgman, G. R. Guntenspergen, and W. G. Shriver, “Estimates of tidal-marsh bird densities using bayesian networks,” The Journal of Wildlife Management, vol.83, no.1, pp.109–120, 2019.
  • [7] D. Taylor, L. Samie, and C. Champod, “Using bayesian networks to track dna movement through complex transfer scenarios,” Forensic Science International: Genetics, vol. 42, pp. 69-80, 2019.
  • [8] D. Dinis, A. Barbosa-Póvoa, and Â. P. Teixeira, “Valuing data in aircraft maintenance through big data analytics: A probabilistic approach for capacity planning using bayesian networks,” Computers & Industrial Engineering, vol.128, pp.920–936, 2019.
  • [9] D. M. Chickering, “Learning Bayesian networks is NP-complete,” in Learning from Data, Springer, pp.121–130, 1996.
  • [10] R. W. Robinson, “Counting unlabeled acyclic digraphs,” in Combinatorial mathematics V, pp.28–43, Springer, 1977.
  • [11] N. Friedman, “Learning belief networks in the presence of missing values and hidden variables,” in ICML, vol.97, pp.125–133, 1997.
  • [12] N. Friedman, “The Bayesian structural em algorithm,” in Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence, pp.129–138, 1998.
  • [13] P. Spirtes, C. N. Glymour, and R. Scheines. Causation, prediction, and search, vol.81. MIT press, 2000.
  • [14] D. Margaritis, “Learning bayesian network model structure from data,” tech. rep., Carnegie-Mellon University Pittsburgh Pa School of Computer Science, 2003.
  • [15] S. Yaramakala and D. Margaritis, “Speculative markov blanket discovery for optimal feature selection,” in Fifth IEEE International Conference on Data Mining(ICDM’05), pp.4 pp, IEEE, 2005.
  • [16] X. Qi, X. Fan, Y. Gao, and Y. Liu, “Learning Bayesian network structures using weakest mutual-information first strategy,” International Journal of Approximate Reasoning, vol.114, pp.84–98, 2019.
  • [17] D. Heckerman, D. Geiger, and D. M. Chickering, “Learning Bayesian networks: The combination of knowledge and statistical data,” Machine learning, vol.20, no.3, pp.197–243, 1995.
  • [18] G. F. Cooper and E. Herskovits, “A Bayesian method for the induction of probabilistic networks from data,” Machine learning, vol.9, no.4, pp.309–347, 1992.
  • [19] C. P. De Campos, Z. Zeng, and Q. Ji, “Structure learning of Bayesian networks using constraints,” in Proceedings of the 26th Annual International Conference on Machine Learning, pp.113–120, 2009.
  • [20] C. P. d. Campos and Q. Ji, “Efficient structure learning of bayesian networks using constraints,” Journal of Machine Learning Research, vol.12, pp.663–689, 2011.
  • [21] J. Cussens, “Bayesian network learning with cutting planes,” arXiv preprint arXiv:1202.3713, 2012.
  • [22] T. Jaakkola, D. Sontag, A. Globerson, and M. Meila, “Learning bayesian network structure using lp relaxations,” in Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp.358–365, 2010.
  • [23] M. Teyssier and D. Koller, “Ordering-based search: A simple and effective algorithm for learning Bayesian networks,” arXiv preprint arXiv:1207.1429, 2012.
  • [24] [24] Y. Tang and Z. Xu, “A score based approach towards improving bayesian network structure learning,” in Second International Conference on Advanced Cloud and Big Data, pp.39–44, IEEE, 2014.
  • [25] [25] S. Behjati and H. Beigy, “An order-based algorithm for learning structure of bayesian networks,” in International Conference on Probabilistic Graphical Models, pp.25–36, 2018.
  • [26] I. Tsamardinos, L. E. Brown, and C. F. Aliferis, “The max-min hill-climbing bayesian network structure learning algorithm,” Machine learning, vol. 65, no. 1, pp.31–78, 2006.
  • [27] M. Scutari, P. Howell, D. J. Balding, and I. Mackay, “Multiple quantitative trait analysis using Bayesian networks,” Genetics, vol.198, no.1, pp.129–137, 2014.
  • [28] M. Gasse, A. Aussem, and H. Elghazel, “A hybrid algorithm for bayesian network structure learning with application to multi-label learning,” Expert Systems with Applications, vol.41, no.15, pp.6755–6772, 2014.
  • [29] J. Cussens, M. Järvisalo, J. H. Korhonen, and M. Bartlett, “Bayesian network structure learning with integer programming: Polytopes, facets and complexity,” Journal of Artificial Intelligence Research, vol.58, pp.185–229, 2017.
  • [30] M. Bartlett and J. Cussens, “Advances in bayesian network learning using integer programming,” in proceeding of the 29th conference on Uncertainty in artificial intelligence (UAI2013), p.182–191, UAUI Press, 2013.
  • [31] M. Bartlett and J. Cussens, “Integer linear programming for the bayesian network structure learning problem,” Artificial Intelligence, vol.244, pp.258–271, 2017.
  • [32] J. Cussens, “Maximum likelihood pedigree reconstruction using integer programming.,” in WCB@ ICLP, pp.8–19, 2010.
  • [33] R. Peharz and F. Pernkopf, “Exact maximum margin structure learning of bayesian networks,” arXiv preprint arXiv:1206.6431, 2012.
  • [34] H. S. Farahani and J. Lagergren, “Learning oncogenetic networks by reducing to mixed integer linear programming,” PloS one, vol.8, no.6, p.e65773, 2013.
  • [35] J. A. Gámez, J. L. Mateo, and J. M. Puerta, “Learning bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhood,” Data Mining and Knowledge Discovery, vol.22, no.1, pp.106–148, 2011.
علوم رایانش و فناوری اطلاعات
دوره 17، شماره 2
پاییز و زمستان
پاییز 1398