Подходы к устранению цикличности первичной структуры алгебраической байесовской сети
Ключевые слова:
алгебраическая байесовская сеть, элименирующая последовательность, ацикличностьАннотация
Одним из условий эффективности алгоритмов логико-вероятностного вывода в алгебраической байесовской сети (АБС) является условие ацикличности представляющего её графа. Введение гиперграфового представления структур АБС позволило применять методы преобразования данного графа к ациклическому виду, основывающиеся на методах теории древовидной декомпозиции. Рассмотрена общая схема метода приведения сети к ациклическому виду, использующего элименирующие последовательности. Приведены основные классы эвристических алгоритмов поиска элименирующих последовательностей, применимых в контексте преобразования АБС, а так же оценки их сложности и качества получаемых результатов.Литература
Кормен Т.Х. Алгоритмы: построение и анализ, второе издание : пер. с англ // Кормен, Т.Х. Лейзерсон, Чарльз И., Ривест, Рональд Л. Штайн, Клиффорд. 2-е изд. М.: Вильямс, 2005. 1296 с.
Крейнович В.Я., Нгуен X.Т., Городецкий В И., Нестеров В.М., Тулупьев А Л. Применение интервальных степеней доверия: аналитический обзор // Информационные технологии и интеллектуальные методы. СПб.: СПИИРАН, 1999. Т. 3. С. 6–61
Сироткин А.В. Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2011. Вып. 18. С. 188–214
Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью, СПИИРАН, СПб, 2000, 292 с.
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностные графические модели баз фрагментов знаний с неопределенностью: Диссертация на соискание ученой степени д-ра физ.-мат. Наук. СПб., 2009. 670 с. (Санкт-Петербургский государственный университет)
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство "Анатолия", 2008. 140 с.
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57–61
Тулупьев А.Л., Фильченков А.А., Тулупьева Т.В., Сироткин А.В., Пащенко А.Е., Фроленков К.В., Алексеев А.М., Азаров А.А., Мусина В.Ф., Суворова А.В. Отчет о научно-исследовательской работе «Глобальные структуры алгебраических байесовских сетей. Логико-вероятностный вывод» (промежуточный), инвентарный № 02201351577 от 2013.01.09, по теме «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», регистрационный № 01201259408. СПб.: СПИИРАН, 2013. 210 c.
Фильченков А.А. Иерархия глобальных структур Алгебраической Байесовской Сети как система графов гиперграфов // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2013. Вып. 1 (83). С.75–81
Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей. // Тр. СПИИРАН, 17 (2011), 151–173.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4 (15). С. 136–161.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118.
Фроленков К.В., Фильченков А.А., Тулупьев А.Л. Сиблинговый критерий цикличности минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 25, С. 190–203.
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
Фильченков А.А., Фроленков К.В., Тулупьев А.Л. Устранение циклов во вторичной структуре алгебраической байесовской сети на основе анализа ее четвертичной структуры // Труды СПИИРАН. 2012. Вып. 21. С. 143–156.
Фроленков К. В., Фильченков А. А., Тулупьев А. Л. Апостериорный вывод в третичной полиструктуре алгебраических байесовских сетей // Труды СПИИРАН, 2012 т. 23, C. 343—356.
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.
Amir E. Efficient approximation for triangulation of minimum treewidth // Proc. UAI ’01. MK. 2001. P. 7–15.
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.
Barricelli N. A. Symbiogenetic evolution processes realized by artificial methods. Methodos. 1957. P 143–182.
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.
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
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.
Bouchitte V., Todinca I. Treewidth and minimum fill-in: grouping the minimal separators // SIAM Journal on Computing. 2001. vol 31(1). P. 212–232.
Cano A., Moral S. Heuristic Algorithms for the Triangulation of Graphs // Proceedings of the Fifth IPMU Conference. Springer. 1995. P 166–171.
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.
Fagin R., Halpern J.Y., Megiddo N. A Logic for Reasoning about Probabilities. Report RJ 6190 (60900) 4/12/88. P. 1–41.
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.
Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs. NY: Academic Press. 1980. 286 p.
Holland G. Adaptation in Natural and Artificial Systems. Cambridge. MA: MIT Press. 1992. 211 p.
Halpern J. about Uncertainty. Cambridge. MA: MIT Press. 2003. 483 p.
Kjaerulff U. Triangulation of graphs-algorithms giving small total state space. Aalborg University. Tech. Rep. R-90-09, March 1990.
Kjærulff U. Optimal decomposition of probabilistic networks by simulated annealing. Statistics and Computing. 1992. vol. 2. P. 7–17.
Kloks T. Treewidth: computations and approximations // LNCS. Springer-Verlag. 1994. vol. 842. 218 p.
Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques. MA:MIT Press. 2009. 1231 p.
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.
Łukaszewski T. An evolutionary algorithm for Bayesian network triangulation // Operations Research Proceedings. 2002. P. 365-370.
Luke S. Essentials of Metaheuristics. A Set of Undergraduate Lecture Notes. Zeroth Edition. Online Version 1.2. July, 2011.
Nilsson N.J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 28. P. 71–87.
Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher // Combinatorica. 1994. vol. 14(2). P. 217–241.
Parter. S. The use of linear graphs in Gauss elimination. // SIAM Review. 1961. vol. 3. P. 119–130.
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.
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.
Крейнович В.Я., Нгуен X.Т., Городецкий В И., Нестеров В.М., Тулупьев А Л. Применение интервальных степеней доверия: аналитический обзор // Информационные технологии и интеллектуальные методы. СПб.: СПИИРАН, 1999. Т. 3. С. 6–61
Сироткин А.В. Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2011. Вып. 18. С. 188–214
Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью, СПИИРАН, СПб, 2000, 292 с.
Тулупьев А.Л. Алгебраические байесовские сети: логико-вероятностные графические модели баз фрагментов знаний с неопределенностью: Диссертация на соискание ученой степени д-ра физ.-мат. Наук. СПб., 2009. 670 с. (Санкт-Петербургский государственный университет)
Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство "Анатолия", 2008. 140 с.
Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57–61
Тулупьев А.Л., Фильченков А.А., Тулупьева Т.В., Сироткин А.В., Пащенко А.Е., Фроленков К.В., Алексеев А.М., Азаров А.А., Мусина В.Ф., Суворова А.В. Отчет о научно-исследовательской работе «Глобальные структуры алгебраических байесовских сетей. Логико-вероятностный вывод» (промежуточный), инвентарный № 02201351577 от 2013.01.09, по теме «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», регистрационный № 01201259408. СПб.: СПИИРАН, 2013. 210 c.
Фильченков А.А. Иерархия глобальных структур Алгебраической Байесовской Сети как система графов гиперграфов // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2013. Вып. 1 (83). С.75–81
Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей. // Тр. СПИИРАН, 17 (2011), 151–173.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4 (15). С. 136–161.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118.
Фроленков К.В., Фильченков А.А., Тулупьев А.Л. Сиблинговый критерий цикличности минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 25, С. 190–203.
Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
Фильченков А.А., Фроленков К.В., Тулупьев А.Л. Устранение циклов во вторичной структуре алгебраической байесовской сети на основе анализа ее четвертичной структуры // Труды СПИИРАН. 2012. Вып. 21. С. 143–156.
Фроленков К. В., Фильченков А. А., Тулупьев А. Л. Апостериорный вывод в третичной полиструктуре алгебраических байесовских сетей // Труды СПИИРАН, 2012 т. 23, C. 343—356.
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.
Amir E. Efficient approximation for triangulation of minimum treewidth // Proc. UAI ’01. MK. 2001. P. 7–15.
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.
Barricelli N. A. Symbiogenetic evolution processes realized by artificial methods. Methodos. 1957. P 143–182.
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.
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
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.
Bouchitte V., Todinca I. Treewidth and minimum fill-in: grouping the minimal separators // SIAM Journal on Computing. 2001. vol 31(1). P. 212–232.
Cano A., Moral S. Heuristic Algorithms for the Triangulation of Graphs // Proceedings of the Fifth IPMU Conference. Springer. 1995. P 166–171.
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.
Fagin R., Halpern J.Y., Megiddo N. A Logic for Reasoning about Probabilities. Report RJ 6190 (60900) 4/12/88. P. 1–41.
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.
Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs. NY: Academic Press. 1980. 286 p.
Holland G. Adaptation in Natural and Artificial Systems. Cambridge. MA: MIT Press. 1992. 211 p.
Halpern J. about Uncertainty. Cambridge. MA: MIT Press. 2003. 483 p.
Kjaerulff U. Triangulation of graphs-algorithms giving small total state space. Aalborg University. Tech. Rep. R-90-09, March 1990.
Kjærulff U. Optimal decomposition of probabilistic networks by simulated annealing. Statistics and Computing. 1992. vol. 2. P. 7–17.
Kloks T. Treewidth: computations and approximations // LNCS. Springer-Verlag. 1994. vol. 842. 218 p.
Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques. MA:MIT Press. 2009. 1231 p.
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.
Łukaszewski T. An evolutionary algorithm for Bayesian network triangulation // Operations Research Proceedings. 2002. P. 365-370.
Luke S. Essentials of Metaheuristics. A Set of Undergraduate Lecture Notes. Zeroth Edition. Online Version 1.2. July, 2011.
Nilsson N.J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 28. P. 71–87.
Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher // Combinatorica. 1994. vol. 14(2). P. 217–241.
Parter. S. The use of linear graphs in Gauss elimination. // SIAM Review. 1961. vol. 3. P. 119–130.
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.
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.
Опубликован
2013-06-01
Как цитировать
Вяткин, А. В., Фильченков, А. А., Тулупьев, А. Л., Мусина, В. Ф., & Фроленков, К. В. (2013). Подходы к устранению цикличности первичной структуры алгебраической байесовской сети. Труды СПИИРАН, 3(26), 216-233. https://doi.org/10.15622/sp.26.16
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
