Алгебраические байесовские сети: проверка магистральной связности
DOI:
https://doi.org/10.21638/spbu01.2021.210Аннотация
В работе исследуется одна из задач, возникающих при машинном обучении баз фрагментов знаний с неопределенностью, представленных в виде алгебраических байесовских сетей - построение графа смежности как глобальной структуры сети по ее первичной структуре. Цель исследования заключается в предложении методов решения обратной задачи. В качестве результатов предложены алгоритмы проверки графа на принадлежность семейству графов смежности и семейству минимальных графов смежности, сделаны оценки их вычислительной сложности. Для алгоритма проверки принадлежности семейству графов смежности также предложена улучшенная версия для частного случая и улучшение для общего случая в среднем. Вопрос распознавания графов смежности ранее не исследовался, в текущей формулировке ставится и решается впервые. Теоретическая значимость заключается в возможностях для применения результатов в дальнейших исследованиях теоретико-графовых инвариантов в глобальных структурах алгебраических байесовских сетей.Ключевые слова:
алгебраические байесовские сети, граф смежности, минимальный граф смежности, алгоритмы на графах, сложность алгоритмов
Скачивания
Данные скачивания пока недоступны.
Библиографические ссылки
Литература
1. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях. Труды СПИИРАН, (5), 71–99 (2007).
2. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности. Труды СПИИРАН, (11), 142–157 (2009).
3. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логиковероятностный вывод в ациклических направленных графах. Санкт-Петербург, Изд-во С.-Петерб. ун-та (2009).
4. Фильченков А.А. Субоптимальная звездчатая структура алгебраической байесовской сети. Информационно-управляющие системы, (2), 13–17 (2013).
5. Опарин В.В., Фильченков А.А., Сироткин А.В., Тулупьев А.Л. Матроидное представление семейства графов смежности над набором фрагментов знаний. Научно-технический вестник информационных технологий, механики и оптики, (4), 73–76 (2010).
6. Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier (2014).
7. Rue H., Held L. Gaussian Markov random fields: theory and applications. CRC Press (2005).
8. Kharitonov N.A., Maximov A.G., Tulupyev A.L. Algebraic Bayesian Networks: Na¨ıve Frequentist Approach to Local Machine Learning Based on Imperfect Information from Social Media and Expert Estimates. Russian Conference on Artificial Intelligence. Springer, Cham, 234–244 (2019).
9. Madsen A. L., Jensen F., Salmer´on A., Langseth H., Nielsen T.D. A parallel algorithm for Bayesian network structure learning from large data sets. Knowledge-Based Systems 117, 46–55 (2017).
10. Baltruˇsaitis T., Ahuja C., Morency L.P. Multimodal machine learning: A survey and taxonomy. IEEE transactions on pattern analysis and machine intelligence 41 (2), 423–443 (2018).
11. Sawada K., Hashimoto K., Nankaku Y., Tokuda K. A Bayesian framework for image recognition based on hidden Markov eigen-image models. IEEJ Transactions on Electrical and Electronic Engineering 13 (9), 1335–1347 (2018).
12. Cai B., Kong X., Liu Y., Lin J., Yuan X., Xu H., Ji R. Application of Bayesian networks in reliability evaluation. IEEE Transactions on Industrial Informatics 15 (4), 2146–2157 (2018).
13. Ghahramani Z. Probabilistic machine learning and artificial intelligence. Nature 521 (7553), 452–459 (2015).
14. Smirnov S. Towards conformal invariance of 2D lattice models. Proceedings of the International Congress of Mathematicians (ICM), Madrid, Spain, August 22–30, 2006. Vol. II, 1421–1451. Z¨urich, European Mathematical Society (2006).
15. Schmidt J.M. The Mondschein sequence. In: Lecture Notes in Computer Science, 967–978 (2014).
16. Cormen T.H., Leiserson C.E., Rivest R. L., Stein C. Introduction to algorithms. MIT Press (2009).
17. Tarjan R.E. Efficiency of a good but not linear set union algorithm. Journal of the ACM (JACM) 22 (2), 215–225 (1975).
18. Tarjan R.E., Van Leeuwen J. Worst-case analysis of set union algorithms. Journal of the ACM (JACM) 31 (2), 245–281 (1984).
19. Fredman M., Saks M. The cell probe complexity of dynamic data structures. Proceedings of the twenty-first annual ACM symposium on Theory of computing, 345–354 (1989).
20. Lancia G., Vidoni P. Finding the largest triangle in a graph in expected quadratic time. European Journal of Operational Research 286 (2), 458–467 (2020).
21. Spielman D.A., Shang-Hua T. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) 51 (3), 385–463 (2004).
22. Bollob´as B. Modern graph theory. Vol. 184. Springer Science & Business Media (2013).
23. Schmidt J.M. A simple test on 2-vertex-and 2-edge-connectivity. Information Processing Letters 113 (7), 241–244 (2013).
24. Szegedy B., Szegedy C. Symplectic spaces and ear-decomposition of matroids. Combinatorica 26 (3), 353–377 (2006).
25. Whitney H. Non-separable and planar graphs. In: Classic Papers in Combinatorics. Modern Birkh¨auser Classics. Boston, Birkh¨auser, 25–48 (2009). https://doi.org/10.1007/978-0-8176-4842-8_2
26. Shang X., Chao T., Ma P., Yang M. An efficient local search-based genetic algorithm for constructing optimal Latin hypercube design. Engineering Optimization 52 (2), 271–287 (2020).
27. Ghoshal S., Sundar S. Two heuristics for the rainbow spanning forest problem. European Journal of Operational Research 285 (3), 853–864 (2020).
28. Корепанова А.А., Абрамов М.В., Тулупьева Т.В. Идентификация аккаунтов пользователей в социальных сетях "Вконтакте" и "Одноклассники". Семнадцатая Национальная конференция по искусственному интеллекту с международным участием (КИИ-2019). Ульяновск, 21–25 октября 2019, Ульяновск, УлГТУ. Т. 2, 153–163 (2019).
29. Shindarev N., Bagretsov G., Abramov M., Tulupyeva T., Suvorova A. Approach to identifying of employees’ profiles in websites of social networks aimed to analyze social engineering vulnerabilities. Advances in Intelligent Systems and Computing 679, 441–447 (2018). https://doi.org/10.1007/978-3-319-68321-8_45
30. Khlobystova A.O., Abramov M.V., Tulupyev A.L. An approach to estimating of criticality of social engineering attacks traces. In: Studies in Systems, Decision and Control 199, 446–456 (2019).
References
1. Tulupyev A. L., Stolyarov D.M., Mentyukov M.V. Representation of the local and global structure of a Bayesian algebraic network in Java applications. SPIIRAS Proceedings, (5), 71–99 (2007). (In Russian)
2. Oparin V.V., Tulupyev A.L. Synthesis of a joint graph with a minimum number of edges: formalization of the algorithm and analysis of its correctness. SPIIRAS Proceedings, (11), 142–157 (2009). (In Russian)
3. Tulupyev A. L., Sirotkin A.V., Nikolenko S.I. Bayesian beliefe networks: logical probabilistic inference in acyclic directed graphs. St. Petersburg, St.Petersburg University Press (2009). (In Russian)
4. Filchenkov A.A., Tulupyev A. L., Sirotkin A.V. The power of the set of minimal joint graphs. Information and Control Systems 15, 136–161 (2010). (In Russian)
5. Oparin V.V., Filchenkov A.A., Sirotkin A.V., Tulupyev A. L. Matroid representation of a family of joint graphs over a set of knowledge fragments. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, (4), 73–76 (2010). (In Russian)
6. Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier (2014).
7. Rue H., Held L. Gaussian Markov random fields: theory and applications. CRC Press (2005).
8. Kharitonov N.A., Maximov A.G., Tulupyev A. L. Algebraic Bayesian Networks: Na¨ıve Frequentist Approach to Local Machine Learning Based on Imperfect Information from Social Media and Expert Estimates. Russian Conference on Artificial Intelligence. Springer, Cham, 234–244 (2019).
9. Madsen A. L., Jensen F., Salmer´on A., Langseth H., Nielsen T.D. A parallel algorithm for Bayesian network structure learning from large data sets. Knowledge-Based Systems 117, 46–55 (2017).
10. Baltruˇsaitis T., Ahuja C., Morency L.P. Multimodal machine learning: A survey and taxonomy. IEEE transactions on pattern analysis and machine intelligence 41 (2), 423–443 (2018).
11. Sawada K., Hashimoto K., Nankaku Y., Tokuda K. A Bayesian framework for image recognition based on hidden Markov eigen-image models. IEEJ Transactions on Electrical and Electronic Engineering 13 (9), 1335–1347 (2018).
12. Cai B., Kong X., Liu Y., Lin J., Yuan X., Xu H., Ji R. Application of Bayesian networks in reliability evaluation. IEEE Transactions on Industrial Informatics 15 (4), 2146–2157 (2018).
13. Ghahramani Z. Probabilistic machine learning and artificial intelligence. Nature 521 (7553), 452–459 (2015).
14. Smirnov S. Towards conformal invariance of 2D lattice models. Proceedings of the International Congress of Mathematicians (ICM), Madrid, Spain, August 22–30, 2006. Vol. II, 1421–1451. Z¨urich, European Mathematical Society (2006).
15. Schmidt J.M. The Mondschein sequence. In: Lecture Notes in Computer Science, 967–978 (2014).
16. Cormen T.H., Leiserson C.E., Rivest R. L., Stein C. Introduction to algorithms. MIT Press (2009).
17. Tarjan R.E. Efficiency of a good but not linear set union algorithm. Journal of the ACM 22 (2), 215–225 (1975).
18. Tarjan R.E., Van Leeuwen J. Worst-case analysis of set union algorithms. Journal of the ACM (JACM) 31 (2), 245–281 (1984).
19. Fredman M., Saks M. The cell probe complexity of dynamic data structures. Proceedings of the twenty-first annual ACM symposium on Theory of computing, 345–354 (1989).
20. Lancia G., Vidoni P. Finding the largest triangle in a graph in expected quadratic time. European Journal of Operational Research 286 (2), 458–467 (2020).
21. Spielman D.A., Shang-Hua T. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) 51 (3), 385–463 (2004).
22. Bollob´as B. Modern graph theory. Vol. 184. Springer Science & Business Media (2013).
23. Schmidt J.M. A simple test on 2-vertex-and 2-edge-connectivity. Information Processing Letters 113 (7), 241–244 (2013).
24. Szegedy B., Szegedy C. Symplectic spaces and ear-decomposition of matroids. Combinatorica 26 (3), 353–377 (2006).
25. Whitney H. Non-separable and planar graphs. In: Classic Papers in Combinatorics. Modern Birkh¨auser Classics. Boston, Birkh¨auser, 25–48 (2009). https://doi.org/10.1007/978-0-8176-4842-8_2
26. Shang X., Chao T., Ma P., Yang M. An efficient local search-based genetic algorithm for constructing optimal Latin hypercube design. Engineering Optimization 52 (2), 271–287 (2020).
27. Ghoshal S., Sundar S. Two heuristics for the rainbow spanning forest problem. European Journal of Operational Research 285 (3), 853–864 (2020).
28. Korepanova A.A., Oliseenko V.D., Abramov M.V., Tulupyev A.L. Application of machine learning methods in the task of identifying user accounts in two social networks. Computer tools in education, (3), 29–43 (2019). https://doi.org/10.32603/2071-2340-2019-3-29-43
29. Shindarev N., Bagretsov G., Abramov M., Tulupyeva T., Suvorova A. Approach to identifying of employees’ profiles in websites of social networks aimed to analyze social engineering vulnerabilities. Advances in Intelligent Systems and Computing 679, 441–447 (2018). https://doi.org/10.1007/978-3-319-68321-8_45
30. Khlobystova A.O., Abramov M.V., Tulupyev A.L. An approach to estimating of criticality of social engineering attacks traces. In: Studies in Systems, Decision and Control 199, 446–456 (2019).
Загрузки
Опубликован
21.07.2021
Как цитировать
Максимов, А. Г., & Тулупьев, А. Л. (2021). Алгебраические байесовские сети: проверка магистральной связности. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 8(2), 305–316. https://doi.org/10.21638/spbu01.2021.210
Выпуск
Раздел
Математика
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
