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

Предмет исследования. Алгебраические байесовские сети относятся к классу вероятностных графических моделей, являющихся представлением баз знаний с неопределенностью. Отличительной особенностью алгебраических байесовских сетей является наличие глобальных структур, среди которых присутствуют первичная и вторичная, которые используются в различных видах логико-вероятностного вывода непосредственно, а также третичная и четвертичная, участвующие в задачах автоматического синтеза, идентификации свойств вторичной структуры и, опосредованно, в решении задач машинного обучения указанных сетей. Существующие алгоритмы изменения четвертичной структуры требуют ее полного перестроения при изменении первичной структуры. Эта особенность замедляет синтез глобальных структур, рассеивает внимание пользователя, вынужденного заново анализировать всю перестроенную структуру, а не концентрироваться лишь на тех изменениях, которые были непосредственно обусловлены ограниченной модификацией исходных данных, что снижает привлекательность алгебраических байесовских сетей как модели для обработки и визуализации данных в целом. Цель исследования. Работа направлена на локализацию изменений четвертичной структуры при добавлении и удалении вершины из первичной структуры или, иначе говоря, на обеспечение ограничения таких изменений лишь необходимыми из них за счет устранения недостатка существующих алгоритмов, выраженного в избыточном перестроении всей структуры. Для достижения поставленной цели решается задача инкрементализации алгоритма перестроения четвертичной структуры. Метод. Предлагаемый подход основан на свойствах инкрементализации алгоритмов, позволяющих сократить объем вычислений за счет использования результата, полученного на предыдущем шаге алгоритма. Все рассуждения, проводимые в работе, изложены на языке теории графов, чтобы использовать устоявшуюся систему терминов и классических результатов. Основные результаты. В работе представлены инкрементальный и декрементальный алгоритмы изменения четвертичной структуры при добавлении или удалении вершины из первичной структуры алгебраической байесовской сети, снабженные доказательством корректности и листингами. Приведенные в работе алгоритмы строятся на основании полученных ранее инкрементальных алгоритмов для третичной структуры. Также в работе проводится подробный анализ множества сепараторов на каждом этапе работы алгоритмов. Теоретическая и практическая значимость. Полученные алгоритмы развивают теорию глобальных структур алгебраических байесовских сетей, в частности, и теорию вероятностных графических моделей в целом. Кроме того, они создают задел для поиска инвариантного представления системы связей внутри алгебраической байесовской сети в отличие от существующего подхода, при котором эти связи выражены во вторичной структуре, которая может оказаться не единственной даже при фиксированной первичной структуре. Исключение манипуляций с множеством вторичных структур заметно упростит и сделает обозримой визуализацию такого сложного объекта, как алгебраические байесовские сети, и, возможно, улучшит вычислительные характеристики алгоритмов логико-вероятностного вывода в сети, а также позволит переформулировать задачи машинного обучения алгебраических байесовских сетей, исключив из них необходимость синтеза множества разных объектов сложной структуры с фактически одинаковой семантикой. Также можно ожидать, что полученные инкрементальные алгоритмы ускорят вычислительные процессы по перестроению и анализу свойств всех четырех глобальных структур алгебраических байесовских сетей.

1. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети доверия: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
2. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: СПбГУ, 2009. 400 с.
3. Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. СПб.: СПбГУ-Анатолия, 2007. 80 с.
4. Kabir G., Sadiq R., Tesfamariam S. A fuzzy Bayesian belief network for safety assessment of oil and gas pipelines // Structure and Infrastructure Engineering. 2016. V. 12. N 8. P. 874–889. doi: 10.1080/15732479.2015.1053093
5. John A., Yang Z., Riahi R., Wang J. A risk assessment approach to improve the resilience of a seaport system using Bayesian networks // Ocean Engineering. 2016. V. 111. P. 136–147. doi: 10.1016/j.oceaneng.2015.10.048
6. Zarikas V., Papageorgiou E., Regner P. Bayesian network construction using a fuzzy rule based approach for medical decision support // Expert Systems. V. 32. N 3. P. 344–369. doi: 10.1111/exsy.12089
7. Zhang Q. Dynamic uncertain causality graph for knowledge representation and reasoning: continuous variable, uncertain evidence, and failure forecast // IEEE Transactions on Systems Man, and Cybernetics: Systems. 2015. V. 45. N 7. P. 990–1003. doi: 10.1109/TSMC.2015.2392711
8. Зотов М.А., Левенец Д.Г., Тулупьев А.Л., Золотин А.А. Синтез вторичной структуры алгебраических байесовских сетей: инкрементальный алгоритм и статистическая оценка его сложности // Научно-технический вестник информационных технологий, механики и оптики. 2016.
Т. 16. №1. С. 122–132. doi: 10.17586/2226-1494-2016-16-1-122-132
9. Banerjee S., Ghosal S. Bayesian structure learning in graphical models // Journal of Multivariate Analysis. 2015. V. 136. P. 147–162. doi: 10.1016/j.jmva.2015.01.015
10. Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. № 2. С. 151–173.
11. Фильченков А.А., Тулупьев А.Л. Алгоритм выявления ацикличности первичной структуры алгебраической байесовской сети по ее четвертичной структуре // Труды СПИИРАН. 2011. № 4(19). С. 128–145.
12. Фильченков А.А. Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей. Дис. ... канд. физ.-мат. наук. Самара, 2013. 339 с.
13. Фильченков А.А., Тулупьев А.Л. Третичная структура алгебраической байесовской сети // Труды СПИИРАН. 2011. № 3(18). С. 164–187.
14. Bernstein A. Maintaining shortest paths under deletions in weighted directed graphs // SIAM Journal on Computing. 2016. V. 45. N 2. P. 548–574. doi: 10.1137/130938670
15. Soulignac F.J. Fully dynamic recognition of proper circular-arc graphs // Algorithmica. 2015. V. 71. N 4. P. 904–968. doi: 10.1007/s00453-013-9835-7
16. Lu G.-F., Zou J., Wang Y. A new and fast implementation of orthogonal LDA algorithm and its incremental extension // Neural Processing Letters. 2016. V. 43. N 3. P. 687–707. doi: 10.1007/s11063-015-9441-6
17. Feng L., Wang Y., Zuo W. Quick online spam classification method based on active and incremental learning // Journal of Intelligent and Fuzzy Systems. 2016. V. 30. N 1. P 17–27. doi: 10.3233/IFS-151707
18. Chen M.-H., Chang P.-C., Wu J.-L. A population-based incremental learning approach with artificial immune system for network intrusion detection // Engineering Applications of Artificial Intelligence. 2016. V. 51. P. 171–181. doi: 10.1016/j.engappai.2016.01.020
19. Levenets D.G., Zotov M.A., Romanov A.V., Tulupyev A.L., Zolotin A.A., Filchenkov A.A. Decremental and incremental reshaping of algebraic Bayesian networks global structures // Proc. 1st Int. Scientific Conference on Intelligent Information Technologies for Industry (IITI’16). Sochi, Russia, 2016. P. 57–67. doi: 10.1007/978-3-319-33816-3_6
20. Романов А.В., Левенец Д.Г., Золотин А.А., Тулупьев А.Л. Инкрементальный синтез третичной структуры алгебраических байесовских сетей // Сборник докладов Международной конференции по мягким вычислениям и измерениям (SCM-2016). Санкт-Петербург, 2016. Т. 1. С. 27–29.
21. Зотов М.А., Тулупьев А.Л. Синтез вторичной структуры алгебраических байесовских сетей: методика статистической оценки сложности и компаративный анализ прямого и жадного алгоритмов // Компьютерные инструменты в образовании. 2015. № 1. С. 3–18.
22. Зотов М.А., Тулупьев А.Л., Сироткин А.В. Статистические оценки сложности прямого и жадного алгоритмов синтеза вторичной структуры алгебраических байесовских сетей // Нечеткие системы и мягкие вычисления. 2015. Т. 10. № 1. С. 75–91.
 

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