УДК 004.8+519.2

ПРЕОБРАЗОВАНИЕ ПЕРВИЧНОЙ СТРУКТУРЫ АЛГЕБРАИЧЕСКОЙ БАЙЕСОВСКОЙ СЕТИ К АЦИКЛИЧЕСКОЙ С СОХРАНЕНИЕМ ВЕРОЯТНОСТНОЙ СЕМАНТИКИ

А.А. Фильченков

Аннотация


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

Ключевые слова


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

Полный текст:

PDF

Литература


  1. Dechter R. Constraint processing. San Francisco: Morgan Kaufmann, 2003. 481 p.
  2. Dechter R., Pearl J. Tree clustering for constraint networks // Artificial Intelligence. 1989. Vol. 38(3). P. 353–366
  3. Fagin R. Degrees of acyclicity for hypergraphs and relational database schemes // Journal of the ACM (JACM). 1983. Vol. 30, no. 3. P. 514–550
  4. Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs. NY: Academic Press. 1980. 286 p.
  5. Maier D. Theory of Relational Databases. Rockville, MD: Computer Science Press, 1983. 637 p.
  6. Pearl J. Probabilistic Reasoning in Intelligent Systems. NY: Morgan Kaufmann, 1988. 552 p.
  7. Быкова В.В. Рекуррентные методы вычисления древовидной ширины гиперграфа // Известия ТПУ. 2011. Вып. 5. С. 5–10
  8. Вяткин А.В., Фильченков А.А., Тулупьев А.Л., Мусина В.Ф., Фроленков К.В. Подходы к устранению цикличности первичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2013. Вып. 3(26). С. 216--233
  9. Зыков А.А. Основы теории графов. М.: Наука. 1987. 384 с.
  10. Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью, СПИИРАН, СПб, 2000, 292 с.
  11. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие, Элементы мягких вычислений, СПбГУ, СПб; ООО Издательство «Анатолия», 2007, 40 с.
  12. Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие, Элементы мягких вычислений, СПбГУ, СПб; ООО Издательство «Анатолия», 2007, 80 с.
  13. Тулупьев А.Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость, СПИИРАН, СПб, 1995, 76 с.
  14. Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах, Элементы мягких вычислений, Изд-во С.-Петербургского ун-та, СПб, 2008, 140 с.
  15. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
  16. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
  17. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях. // Труды СПИИРАН. СПб: Наука, 2007. Вып. 5. С. 71–99
  18. Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения. // Информационно-измерительные и управляющие системы. 2011. Вып. 11. С. 57–61
  19. Фильченков А.А. Меры истинности и вероятностные графические модели для представления знаний с неопределенностью // Труды СПИИРАН. 2012. Вып. 4(23). С. 254–295
  20. Фильченков А.А. Протоструктура алгебраической байесовской сети в контексте логико-вероятностного вывода: поддержание связности и ацикличности // Научная сессия НИЯУ МИФИ-2013. (1–6 февраля 2013 г., Москва). Аннотации докладов. В 3 т. Т.2 Проблемы фундаментальной науки. Стратегические информационные технологии. М.: НИЯУ МИФИ, 2013. С. 327
  21. Фильченков А.А., Тулупьев А.Л. Связность и ацикличность первичной структуры алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2013. Вып. 1. C. 110–119
  22. Фильченков А.А., Тулупьев А.Л. Совпадение множеств минимальных и нередуцируемых графов смежности над первичной структурой алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2012. Вып. 2. С. 69–78
  23. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности. // Труды СПИИРАН. СПб: Наука, 2009. Вып. 11. С. 104–127
  24. Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Система алгоритмов синтеза подмножеств минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 4(27). С. 200–244


Андрей Александрович Фильченков - научный сотрудник лаборатории теоретических и междисциплинарных проблем информатики, СПИИРАН.
Область научных интересов: автоматическое обучение вероятностных графических моделей.
Число научных публикаций: 100.

Адрес (E-mail): aaafil@mail.ru
Почтовый адрес: 14-я линия В.О., д. 39, Санкт-Петербург, 199178, РФ
Телефон: +7(812)328-3337
Факс: +7(812)328-4450




DOI: http://dx.doi.org/10.15622/sp.30.10