УДК 004.8

РЕБРА ГРАФОВ СМЕЖНОСТИ В КОНТЕКСТЕ КОМПАРАТИВНОГО АНАЛИЗА КЛИК МИНИМАЛЬНЫХ ГРАФОВ СМЕЖНОСТИ АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ

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

Аннотация


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

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


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

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

PDF

Литература


  1. Городецкий В.И. Алгебраические байесовские сети — новая парадигма экспертно-вычислительных систем // Юбилейный сборник трудов институтов Отделения информатики, вычислительной техники и автоматизации РАН. Т. 2. М.: РАН, 1993, С. 120–141.
  2. Городецкий В.И., Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью // Известия РАН. Сер. Теория и системы управления. 1997. №5. С. 33–42.
  3. Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 73–76.
  4. Павельчук А.В., Тулупьев А.Л., Тотмянина С.А. Подход к объектно-ориентированному представлению данных алгебраических байесовских сетей в java-коде и реляционных СУБД // Региональная информатика-2008 (РИ-2008). XI Санкт-Петербургская международная конференция. Санкт-Петербург, 22–24 октября, 2008 г.: Материалы конференции / СПОИСУ. СПб.: 2009. С. 68–76.
  5. Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. 2009. №11. С. 32–37.
  6. Тотмянина С.А., Павельчук А.В., Тулупьев А.Л. Алгебраические байесовские сети: структуры данных в СУБД и Java- коде // Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интелинтеллекте. Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов (Коломна, 26–27 мая 2009 г.). Научные доклады. В 2-х т. Т. 2. М.: Физматлит, 2009, С. 123–131.
  7. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений).
  8. Тулупьев А.Л. Алгебраические байесовские сети: реализация логико-вероятностного вывода в комплексе java-программ // Труды СПИИРАН. СПб.: Наука, 2009. Вып. 8. С. 191–232.
  9. Тулупьев А.Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Том 1, № 1. С. 57–93.
  10. Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Элементы мягких вычислений.) 11. Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях. Вестник СПбГУ. Сер. 10. 2009. Вып. 3. С. 144–151.
  11. Тулупьев А.Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях. Вестник СПбГУ. Сер. 10. 2009. Вып. 3. С. 144–151.
  12. Тулупьев А.Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. № 3. С. 21–23.
  13. Тулупьев А.Л. Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. № 7. С. 3–8.
  14. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
  15. Тулупьев А.Л., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. № 10. т. 6. С. 85–87.
  16. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.
  17. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях. // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99.
  18. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи клик владений// Труды СПИИРАН. 2010. Вып. 2 (13). [в печати]
  19. Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1 (12). С. 119–133.
  20. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности Труды СПИИРАН. 2009. Вып. 11. С. 104–127.
  21. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализа клик минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 1 (13). [в печати]
  22. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97–118.
  23. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик минимальных графов смежности // Вестник Тверского государственного университета. Сер. Прикладная математика. 2010. [в печати].
  24. Gorodetsky V.I., Drozdgin V.V., Jusupov R.M. Application of Attributed Grammar and Algorithmic Sensitivity Model for Knowledge Representation and Estimation // Artificial Intelligence and Information, Control Systems of ROBOTSA. Amsterdam: Elsevier Science Publishers B. V., 1984, P. 232–237.


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

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


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

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


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

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




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

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.