УДК 004.8

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

А.В. Вяткин, А.А. Фильченков, А.Л. Тулупьев, V.F. Мусина, К.В. Фроленков

Аннотация


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

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


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

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

PDF

Литература


  1. Кормен Т.Х. Алгоритмы: построение и анализ, второе издание : пер. с англ // Кормен, Т.Х. Лейзерсон, Чарльз И., Ривест, Рональд Л. Штайн, Клиффорд. 2-е изд. М.: Вильямс, 2005. 1296 с.
  2. Крейнович В.Я., Нгуен X.Т., Городецкий В И., Нестеров В.М., Тулупьев А Л. Применение интервальных степеней доверия: аналитический обзор // Информационные технологии и интеллектуальные методы. СПб.: СПИИРАН, 1999. Т. 3. С. 6–61
  3. Сироткин А.В. Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2011. Вып. 18. С. 188–214
  4. Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью, СПИИРАН, СПб, 2000, 292 с.
  5. Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностные графические модели баз фрагментов знаний с неопределенностью: Диссертация на соискание ученой степени д-ра физ.-мат. Наук. СПб., 2009. 670 с. (Санкт-Петербургский государственный университет)
  6. Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство "Анатолия", 2008. 140 с.
  7. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
  8. Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57–61
  9. Тулупьев А.Л., Фильченков А.А., Тулупьева Т.В., Сироткин А.В., Пащенко А.Е., Фроленков К.В., Алексеев А.М., Азаров А.А., Мусина В.Ф., Суворова А.В. Отчет о научно-исследовательской работе «Глобальные структуры алгебраических байесовских сетей. Логико-вероятностный вывод» (промежуточный), инвентарный № 02201351577 от 2013.01.09, по теме «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», регистрационный № 01201259408. СПб.: СПИИРАН, 2013. 210 c.
  10. Фильченков А.А. Иерархия глобальных структур Алгебраической Байесовской Сети как система графов гиперграфов // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2013. Вып. 1 (83). С.75–81
  11. Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей. // Тр. СПИИРАН, 17 (2011), 151–173.
  12. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4 (15). С. 136–161.
  13. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118.
  14. Фроленков К.В., Фильченков А.А., Тулупьев А.Л. Сиблинговый критерий цикличности минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 25, С. 190–203.
  15. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
  16. Фильченков А.А., Фроленков К.В., Тулупьев А.Л. Устранение циклов во вторичной структуре алгебраической байесовской сети на основе анализа ее четвертичной структуры // Труды СПИИРАН. 2012. Вып. 21. С. 143–156.
  17. Фроленков К. В., Фильченков А. А., Тулупьев А. Л. Апостериорный вывод в третичной полиструктуре алгебраических байесовских сетей // Труды СПИИРАН, 2012 т. 23, C. 343—356.
  18. Arnborg S., Corneil D.G., Proskurowski A. Complexity of finding embebdings in a K-tree. // SIAM J. Alg. And Discr. Meth. 1987. vol. 8. P. 277–284.
  19. Amir E. Efficient approximation for triangulation of minimum treewidth // Proc. UAI ’01. MK. 2001. P. 7–15.
  20. Amir E., Krauthgamer R., Rao S. Constant factor approximation of vertexcuts in planar graphs // In Proc. 35rd ACM Symp. On Theory of Computing. ACM Press. 2003. P. 90–99.
  21. Barricelli N. A. Symbiogenetic evolution processes realized by artificial methods. Methodos. 1957. P 143–182.
  22. Berry, P. Heggernes, and G. Simonet. The minimum degree heuristic and the minimal triangulation process // Proceedings WG 2003 - 29th Workshop on Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science. Springer Verlag. 2003. vol. 2880. P. 58–70.
  23. Bodlaender H. L., A. Koster, van den Eijkhof F., van der Gaag L. C. Preprocessing for Triangulation of Probabilistic Networks // UAI'01 Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence. 2001. P. 32–39
  24. Bodlaender H. L. Treewidth: Algorithmic techniques and results. In IgorPr´ıvara and Peter Ruzicka, editors. Mathematical Foundations of Computer Science 1997. Springer. vol. 1295. P. 19–36.
  25. Bouchitte V., Todinca I. Treewidth and minimum fill-in: grouping the minimal separators // SIAM Journal on Computing. 2001. vol 31(1). P. 212–232.
  26. Cano A., Moral S. Heuristic Algorithms for the Triangulation of Graphs // Proceedings of the Fifth IPMU Conference. Springer. 1995. P 166–171.
  27. Demaine E. D., Hajiaghayi M. T., Nishimura N., Ragde P., and Thilikos D. M. Approximation algorithms for classes of graphs excluding singlecrossing graphs as minors // Journal of Computer and System Sciences. 2004. vol 69(2). P. 166–195.
  28. Fagin R., Halpern J.Y., Megiddo N. A Logic for Reasoning about Probabilities. Report RJ 6190 (60900) 4/12/88. P. 1–41.
  29. Fagin R., Halpern J.Y. Uncertainty, Belief, and Probability–2 // Proc. of the IEEE Symposium on Logic and Computer Science. 1991. Vol. 7. P. 160–173.
  30. Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs. NY: Academic Press. 1980. 286 p.
  31. Holland G. Adaptation in Natural and Artificial Systems. Cambridge. MA: MIT Press. 1992. 211 p.
  32. Halpern J. about Uncertainty. Cambridge. MA: MIT Press. 2003. 483 p.
  33. Kjaerulff U. Triangulation of graphs-algorithms giving small total state space. Aalborg University. Tech. Rep. R-90-09, March 1990.
  34. Kjærulff U. Optimal decomposition of probabilistic networks by simulated annealing. Statistics and Computing. 1992. vol. 2. P. 7–17.
  35. Kloks T. Treewidth: computations and approximations // LNCS. Springer-Verlag. 1994. vol. 842. 218 p.
  36. Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques. MA:MIT Press. 2009. 1231 p.
  37. Larrañaga P., Kuijpers C., Poza M., Murga R.H. Decomposing Bayesian Networks: Triangulation of Moral Graph with Genetic Algorithms // Statistics and Computing (UK). 1997. 7(1). P. 19–34.
  38. Łukaszewski T. An evolutionary algorithm for Bayesian network triangulation // Operations Research Proceedings. 2002. P. 365-370.
  39. Luke S. Essentials of Metaheuristics. A Set of Undergraduate Lecture Notes. Zeroth Edition. Online Version 1.2. July, 2011.
  40. Nilsson N.J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 28. P. 71–87.
  41. Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher // Combinatorica. 1994. vol. 14(2). P. 217–241.
  42. Parter. S. The use of linear graphs in Gauss elimination. // SIAM Review. 1961. vol. 3. P. 119–130.
  43. Rose D. J., Tarjan R. E., Lueker G. S. Algorithmic aspects of vertex elimination on graphs // SIAM J. Comput. 1976. vol. 5. P. 266–283.
  44. Wang H., Yu K., Wu X., Yao H. Triangulation of Bayesian Networks Using an Adaptive Genetic Algorithm // ISMIS. volume 4203 of Lecture Notes in Computer Science, Springer. 2006. P. 127–136.


Андрей Валерьевич Вяткин - студент кафедры информатики математико-механического факультета, С.-Петербургский государственный университет (СПбГУ).
Область научных интересов: машинное обучение.


Адрес (E-mail): dewshick@gmail.com
Почтовый адрес: Университетский проспект, д. 28, Старый Петергоф, 198504, Санкт-Петербург, РФ
Телефон: +7(812)328-3337
Факс: +7(812)328-4450


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

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


Александр Львович Тулупьев - д.ф.-м.н., проф., заведующий лабораторией теоретических и междисциплинарных проблем информатики, СПИИРАН, доцент кафедры информатики математико-механического факультета, С.-Петербургский государственный университет (СПбГУ).
Область научных интересов: представление и обработка данных и знаний с неопределенностью, применение методов математики и информатики в социокультурных исследованиях, применение методов биостатистики и математического моделирования в эпидемиологии.
Число научных публикаций: 250.

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


Валерия Фуатовна Мусина - младший научный сотрудник лаборатории теоретических и междисциплинарных проблем информатики, СПИИРАН, студент магистратуры экономического факультета, С.-Петербургский государственный университет (СПбГУ).
Область научных интересов: случайные процессы, вероятностное и статистическое моделирование, биостатистика, вероятностные графические модели.
Число научных публикаций: 13.

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


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

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




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