УДК 004.8

АЛГОРИТМ РАНДОМИЗИРОВАННОГО СИНТЕЗА МИНИМАЛЬНОГО ГРАФА СМЕЖНОСТИ

А.А. Фильченков, В.Ф. Мусина, А.Л. Тулупьев

Аннотация


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

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


ключевые байесовские сети, вторичная структура, графы смежности, автоматическое обучение, случайные графы

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

PDF

Литература


  1. Райгородский А.М. Модели случайных графов и их применение // Тр. МФТИ. 2010. Т.2. №4. С. 130–140
  2. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Труды СПИИРАН. СПб.: Наука, 2009. Вып. 11. С. 142–157
  3. Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт- Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76
  4. Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37
  5. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб.пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер.Элементы мягких вычислений)
  6. Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 292 с.
  7. Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб.пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 80 с. (Сер.Элементы мягких вычислений)
  8. Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Том 1, № 1. С. 57–93
  9. Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений)
  10. Тулупьев А.Л. Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. №7. С. 3–8
  11. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
  12. Тулупьев А.Л., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. № 10. т. 6. С. 85–87
  13. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. Ун-та, 2009, 400 с.
  14. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99
  15. Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57-61
  16. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133
  17. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3 (14) С. 150–169
  18. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2 (13). С. 119–133
  19. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4 (15). С. 193–212
  20. Фильченков А.А. Иерархия глобальных структур алгебраической байесовской сети как система графов и гиперграфов // Научно-технический вестник информационных технологий, механики и оптики. 2013. Вып. 1(83). С. 75–80
  21. Фильченков А.А. Меры истинности и вероятностные графические модели для представления знаний с неопределенностью // Труды СПИИРАН. 2012. Вып. 4(23). С. 254–295
  22. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. Вып. 11. С. 104–127
  23. Фильченков А.А., Тулупьев А.Л. Третичная структура алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 18. С. 164–187
  24. Фильченков А.А., Тулупьев А.Л. Совпадение множеств минимальных и нередуцируемых графов смежности над первичной структурой алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2012. Вып. 2. С. 65–74
  25. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118
  26. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестн. Тверск. гос. ун-та. Сер.: Прикладная математика. 2011. №20. С. 139–151
  27. Ширяев А.Н. Вероятность. М.: Наука, 1989. 640 с.
  28. Barabási A.-L., Albert R. Emergence of Scaling in Random Networks// Science. Vol.286. №.5439. P. 509-512
  29. Bollobás B. Random Graphs. 2nd ed. Cambridge University Press. 2001. 498 p.
  30. Erdős P., Rényi A. On random graphs. I // Publ. Math.1959. P. 290–297
  31. Erdős P., Rényi A. On the evolution of random graphs // Magyar Tud. Akad. Mat. Kutató Int. Közl. 1960. №5. P. 17–61
  32. Erdős P., Rényi A. On the evolution of random graphs // Bull. Inst. Internat. Statist. 1961. №38. P. 343–347
  33. Erdős P., Rényi A. On the strength of connectedness of a random graph // Acta Math. Acad. Sci. Hungar. 1961. №12. P. 261–267
  34. Gilbert E.N. Random Graphs // Annals of Mathematical Statistics.1959. № 30 (4). P. 1141–1144
  35. Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques . The MIT Press, 2009. 1208 p.
  36. van der Hofstad R. Random graphs and complex networks. Lecture notes. // Available on http://www.win.tue.nl/rhofstad/NotesRGCN.pdf
  37. Strogatz S.H. Exploring complex networks // Nature. 2001. №410. P. 268–276. doi:10.1038/35065725


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

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


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

Адрес (E-mail): valery.musina@gmail.ru
Почтовый адрес: 14-я линия В.О., д. 39, Санкт-Петербург, 199178, РФ
Телефон: +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




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