|
МАТЕМАТИКА
Алгебраические байесовские сети: проверка магистральной связности
А. Г. Максимовa, А. Л. Тулупьевba a Санкт-Петербургский федеральный исследовательский центр РАН, Российская Федерация, 199178, 14-я линия B.O., 39
b Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9
Аннотация:
В работе исследуется одна из задач, возникающих при машинном обучении баз фрагментов знаний с неопределенностью, представленных в виде алгебраических байесовских сетей - построение графа смежности как глобальной структуры сети по ее первичной структуре. Цель исследования заключается в предложении методов решения обратной задачи. В качестве результатов предложены алгоритмы проверки графа на принадлежность семейству графов смежности и семейству минимальных графов смежности, сделаны оценки их вычислительной сложности. Для алгоритма проверки принадлежности семейству графов смежности также предложена улучшенная версия для частного случая и улучшение для общего случая в среднем. Вопрос распознавания графов смежности ранее не исследовался, в текущей формулировке ставится и решается впервые. Теоретическая значимость заключается в возможностях для применения результатов в дальнейших исследованиях теоретико-графовых инвариантов в глобальных структурах алгебраических байесовских сетей.
Ключевые слова:
алгебраические байесовские сети, граф смежности, минимальный граф смежности, алгоритмы на графах, сложность алгоритмов.
Поступила в редакцию: 20.07.2020 Исправленный вариант: 03.09.2020 Принята в печать: 17.12.2020
Образец цитирования:
А. Г. Максимов, А. Л. Тулупьев, “Алгебраические байесовские сети: проверка магистральной связности”, Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 8:2 (2021), 305–316; Vestn. St. Petersbg. Univ., Math., 8:3 (2021), 187–195
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vspua117 https://www.mathnet.ru/rus/vspua/v8/i2/p305
|
Статистика просмотров: |
Страница аннотации: | 41 | PDF полного текста: | 6 |
|