УДК 004.8

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

А.А. Фильченков, К.В. Фроленков, А.В. Сироткин, А.Л. Тулупьев

Аннотация


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

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


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

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

PDF

Литература


  1. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Труды СПИИРАН. СПб.: Наука, 2009. Вып. 11. С. 142–157.
  2. Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт- Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76
  3. Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37.
  4. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений).
  5. Тулупьев А.Л Алгебраические байесовские сети. Логико-вероятностный подход к моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 292 с.
  6. Тулупьев А.Л Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 80 с. (Сер. Элементы мягких вычислений).
  7. Тулупьев А.Л Ациклические алгебраические байесовские сети: логико-вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Том 1, № 1. С. 57–93.
  8. Тулупьев А.Л Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений).
  9. Тулупьев А.Л Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. №7. С. 3–8.
  10. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
  11. Тулупьев А.Л., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. № 10. т. 6. С. 85–87.
  12. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
  13. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99.
  14. Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57-61.
  15. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133.
  16. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3 (14) С. 150–169.
  17. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2 (13). С. 119–133.
  18. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4 (15). С. 193–212.
  19. Фильченков А.А. Алгоритмы построения третичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 2(17). С. 197–218.
  20. Фильченков А.А. Алгоритмы построения элементов третичной полиструктуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 3 (18). С. 237–266.
  21. Фильченков А.А. Иерархия глобальных структур алгебраической байесовской сети как система графов и гиперграфов // Научно-технический вестник информационных технологий, механики и оптики. 2013. Вып. 1(83). С. 75–80.
  22. Фильченков А.А. Меры истинности и вероятностные графические модели для представления знаний с неопределенностью // Труды СПИИРАН. 2012. Вып. 4(23). С. 254–295.
  23. Фильченков А.А. Субоптимальная звездчатая структура алгебраической байесовской сети // Информационно-управляющие системы. 2013. Вып. 2. С. 13–17.
  24. Фильченков А.А., Мусина В.Ф., Тулупьев А.Л. Алгоритм рандомизированного синтеза минимального графа смежности // Труды СПИИРАН. 2013. Вып. 2(35). С. 221–234.
  25. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
  26. Фильченков А.А., Тулупьев А.Л. Совпадение множеств минимальных и нередуцируемых графов смежности над первичной структурой алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2012. Вып. 2. С. 65–74.
  27. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2 (13). С. 87–105.
  28. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118.
  29. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 3 (14). С. 132–149.
  30. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестн. Тверск. гос. ун-та. Сер.: Прикладная математика. 2011. №20. С. 139–151.
  31. Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms Cambridge, MAThe MIT Press; 3rd edition, 2009. 1312 p.
  32. Prüfer H. Neuer Beweis eines Satzes über Permutationen // Arch. Math. Phys. 1918. No. 27. S. 742–744.


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

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


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

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


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

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


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

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




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