ПОДДЕРЖАНИЕ ИНТЕРНАЛЬНОЙ НЕПРОТИВОРЕЧИВОСТИ АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ С ЛИНЕЙНОЙ И ЗВЕЗДЧАТОЙ СТРУКТУРОЙ

Предмет исследования.При работе с алгебраическими байесовскими сетями необходимо обеспечивать непротиворечивость оценок вероятностей составляющих такие сети элементов. Существует несколько подходов к автоматизации поддержания непротиворечивости, различающихся вычислительной сложностью (временем исполнения). Эта сложность зависит от структуры сети и от выбранного вида непротиворечивости. Выполнено основанное на статистических оценках сравнение времени поддержания интернальной непротиворечивости в алгебраических байесовских сетях с линейной и звездчатой структурой и времени поддержания непротиворечивости фрагмента знаний, покрывающих такие сети. Методоснован на сокращении числа переменных и условий в задачах линейного программирования, решение которых обеспечивает поддержание интернальной непротиворечивости. Проведен эксперимент, демонстрирующий различия между временем поддержания непротиворечивости для различных по глобальной структуре представлений алгебраических байесовских сетей. Основные результаты. Представлена улучшенная версия алгоритма поддержания интернальной непротиворечивости. Упрощены решаемые задачи линейного программирования в сравнении с предыдущей версией алгоритма. Сформулированы и доказаны две теоремы, уточняющие оценки числа переменных и условий в решаемых задачах линейного программирования, а также количества самих задач. Выполнен эксперимент, показавший, что предложенная программная реализация превосходит по скорости работы программную реализацию для полного фрагмента знаний. Практическая значимость. Полученные результаты могут найти применение в машинном обучении алгебраических байесовских сетей (в том числе синтезе их глобальных структур). Предложенный метод позволяет при обучении и дальнейшей обработке сети оптимально синтезировать глобальные ее структуры, для которых достаточно использовать поддержание интернальной непротиворечивости. Благодаря использованию метода эти процессы будут иметь приемлемую вычислительную сложность.

1. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовскиесети: логико-вероятностный подход. СПб: Наука, 2006. 607 с.
2. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовскиесети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб: СПбГУ, 2009. 400 с.
3. Тулупьев А.Л. Алгебраические байесовские сети: локальныйлогико-вероятностный вывод: Учеб. пособие. СПб: СПбГУ-Анатолия, 2007. 80 с.
4. Augustin T., Seising R. Weichselberger's contribution to imprecise probabilities and statistical inference // International Journal of Approximate Reasoning. 2018. V. 98. P. 132–145. doi: 10.1016/j.ijar.2018.04.009
5. Quost B., Destercke S. Classification by pairwise coupling of imprecise probabilities // Pattern Recognition. 2018. V. 77. P. 412–425. doi: 10.1016/j.patcog.2017.10.019
6. Abellan J., Mantas C.J., Castellano J.G., Moral-Garcia S. Increasing diversity in random forest learning algorithm via imprecise probabilities // Expert Systems with Applications. 2018. V. 97. P. 228–243. doi: 10.1016/j.eswa.2017.12.029
7. Zhang J., Shields M.D. On the quantification and efficient propagation of imprecise probabilities resulting from small datasets // Mechanical Systems and Signal Processing. 2018. V. 98. P. 465–483. doi: 10.1016/j.ymssp.2017.04.042
8. Romanov A.V., Levenets D.G., Zolotin A.A., Tulupyev A.L. Incremental synthesis of the tertiary structure of algebraic Bayesian networks // Proc. 19^th Int. Conf. on Soft Computing and Measurements, SCM 2016. St. Petersburg, Russia, 2016. P. 28–30. doi: 10.1109/SCM.2016.7519673
9. Kharitonov N.A., Tulupyev A.L., Zolotin A.A. Software implementation of reconciliation algorithms in algebraic Bayesian networks // Proc. 20^th Int. Conf. on Soft Computing and Measurements, SCM 2017. St. Petersburg, Russia, 2017. P. 8–10.
10. Zolotin A.A., Tulupyev A.L. Sensitivity statistical estimates for local a posteriori inference matrix-vector equations in algebraic Bayesian networks over quantum propositions // Vestnik St. Petersburg University: Mathematics. 2018. V. 51. N 1. P. 42–48. doi: 10.3103/s1063454118010168
11. Kang H.G., Lee S.H. et al. Development of a Bayesian belief network model for software reliability quantification of digital protection systems in nuclear power plants //
    Annals of Nuclear Energy. 2018. V. 120. P. 62–73. doi: 10.1016/j.anucene.2018.04.045
12. Dal F.N., Quinn C., Morari F. A Bayesian belief network framework to predict SOC dynamics of alternative management scenarios // Soil and Tillage Research. 2018. V. 179.
    P. 114–124. doi: 10.1016/j.still.2018.01.002
13. Liu H., Kim J., Shlizerman E. Functional connectomics from neural dynamics: probabilistic graphical models for neuronal network of Caenorhabditis elegans // Philosophical Transactions of the Royal Society B: Biological Sciences. 2018. V. 373. N 1758. doi: 10.1098/rstb.2017.0377
14. Kang Z., Yang J. A probabilistic graphical model for the classification of mobile LiDAR point clouds // ISPRS Journal of Photogrammetry and Remote Sensing. 2018. V. 143. P. 108–123. doi: 10.1016/j.isprsjprs.2018.04.018
15. Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. 2009. № 3. С. 143–150.
16. Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб: СПбГУ, 2008. 140 c.
17. Сироткин А.В. Проверка и поддержание непротиворечивостиалгебраических байесовских сетей: вычислительная сложность алгоритмов // Труды СПИИРАН. 2010. Т. 15. С. 162–192.
18. Dalkiran E., Ghalami L. On linear programming relaxations for solving polynomial programming problems // Computers and Operations Research. 2018. V. 99. P. 67–77.
    doi: 10.1016/j.cor.2018.06.010
19. Kolev L., Skalna I. Exact solution to a parametric linear programming problem // Numerical Algorithms. 2018. V. 78. N 4. P. 1183–1194. doi: 10.1007/s11075-017-0418-6
20. Feng J., Che A. Novel integer linear programming models for the facility layout problem with fixed-size rectangular
    departments // Computers and Operations Research. 2018. V. 95. P. 163–171. doi: 10.1016/j.cor.2018.03.013
21. Абрамов М.В. Автоматизация анализа социальных сетей для оценивания защищённости от социоинженерных атак // Автоматизация процессов управления. 2018. № 1(51). С. 34–40.
22. Азаров А.А., Тулупьева Т.В., Суворова А.В., Тулупьев А.Л.,Абрамов М.В., Юсупов Р.М. Социоинженерные атаки. Проблемы анализа. СПб: Наука, 2016. 352 с.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License