DOI: 10.17586/2226-1494-2018-18-6-1108-1117


УДК004.056.53

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

Харитонов Н.А.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования: Харитонов Н.А. Поддержание интернальной непротиворечивости алгебраических байесовских сетей с линейной и звездчатой структурой // Научно-технический вестник информационных технологий, механики и оптики. 2018. Т. 18. № 6. С. 1108–1117. doi: 10.17586/2226-1494-2018-18-6-1108-1117

Аннотация

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


Ключевые слова: алгебраические байесовские сети, интернальная непротиворечивость, задача линейного программирования, теоретические оценки, эмпирические оценки, фрагмент знаний

Благодарности. Работа выполнена в рамках проекта по государственному заданию СПИИРАН № 0073-2018-0001, при финансовой поддержке РФФИ, проект №18-01-00626 – Методы представления, синтеза оценок истинности и машинного обучения в алгебраических байесовских сетях и родственных моделях знаний с неопределенностью: логико-вероятностный подход и системы графов.

Список литературы
  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. 19th 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. 20th 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 с.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2019 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика