close

Вход

Забыли?

вход по аккаунту

?

Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей.

код для вставкиСкачать
На правах рукописи
ФИЛЬЧЕНКОВ Андрей Александрович
СИНТЕЗ ГРАФОВ СМЕЖНОСТИ
В МАШИННОМ ОБУЧЕНИИ ГЛОБАЛЬНЫХ СТРУКТУР
АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ
05.13.17 Теоретические основы информатики
А В Т О Р Е Ф Е РАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Санкт-Петербург
2013
Работа выполнена на кафедре информатики математико-механического факультета
федерального государственного бюджетного образовательного учреждения высшего
профессионального образования ѕСанкт-Петербургский государственный универститетї и в лаборатории теоретических и междисциплинарных проблем информатики
федерального государственного бюджетного учреждения науки Санкт-Петербургского
института информатики и автоматизации Российской академии наук.
Научный руководитель:
ТУЛУПЬЕВ Александр Львович,
доктор физико-математических наук, доцент
федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования ѕСанктПетербургский государственный университетї, кафедра
информатки, профессор,
федеральное государственное бюджетное учреждение науки
Санкт-Петербургского института информатики и автоматизации Российской академии наук, лаборатория теоретических
и междисциплинарных проблем информатики, заведующий
лабораторией
Официальные оппоненты:
ЯЗЕНИН Александр Васильевич,
доктор физико-математических наук, профессор,
федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования ѕТверской государственный университетї), факультет прикладной
математики и кибернетики, декан
ДОДОНОВА Наталья Леонидовна,
кандидат физико-математических наук, доцент,
федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования ѕСамарский государственный аэрокосмический университет им.
академика С.П. Королева (национальный исследовательский
университет)ї, кафедра прикладной математики, доцент
Ведущая организация:
федеральное государственное бюджетное учреждение науки
Институт системного анализа Российской академии наук
Защита состоится ѕ13ї декабря 2013 г. в 14:00 на заседании диссертационного совета
Д 212.215.07, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования ѕСамарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский
университет)ї (СГАУ), по адресу: 443086, Самара, Московское шоссе, 34.
С диссертацией можно ознакомиться в библиотеке СГАУ.
Автореферат разослан ѕ11ї ноября 2013 г.
Ученый секретарь
диссертационного совета
доктор технических наук, профессор
Белоконов И.В.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Д.А. Поспелов и В.Н. Захаров относили к интеллектуальным методам и технологиям управления в том числе мягкие вычисления, распределенный искусственный интеллект и методы и технологии инженерии знаний и рассуждений на знаниях. Вероятностные графические модели (ВГМ) как область искусственного интеллекта (ИИ) можно отнести к выделенным категориям. Для моделей
этого класса общим является локализация вычислений, основанная на принципе декомпозиции и предположениях об условной независимости. ВГМ представляют собой
граф, узлам которого приписаны случайные элементы, а ребра определенным образом
отображают зависимости между ними.
Алгебраические байесовские сети (АБС), предложенные В.И. Городецким, представляют собой логико-вероятностную графическую модель, опирающуюся на логиковероятностный подход в интерпретации, выдвинутой Н. Нильссоном для теоретических основ и приложений ИИ. Ключевым отличием АБС от других моделей является
представление неопределенности через интервальные оценки вероятности истинности
пропозициональных формул. Проблема представления неопределенности знаний освещалась в работах В.Н. Вагина, Ю.Р. Валькмана, А.С. Нариньяни, Г.С. Осипова, Д.А.
Поспелова, В.Б. Тарасова, Н.Г. Ярушкиной, A. Dempster, D. Dubois, J. Pearl, R. Fagin,
J. Halpern, K. Korb, H. Prade, G. Shafer, L. Zadeh и многих других.
Теория ВГМ нуждается в моделях, методах и алгоритмах машинного (автоматического) обучения1 , в частности, автоматического синтеза глобальных структур таких
моделей и автоматического построения оценок их параметров по исходным данным.
Комплексная проблема глобального обучения АБС заключается в алгоритмизации
синтеза глобальных структур АБС. Среди них выделяют первичную структуру, представляющую собой набор максимальных по включению фрагментов знаний (ФЗ), и
вторичную структуру, в данной работе рассматриваемую как граф, построенный над
элементами первичной структуры и обладающий особым свойством магистральной
связности.
Одной из проблем машинного обучения глобальных структур АБС (глобального
обучения АБС) является синтез по заданной первичной структуре АБС ее вторичной структуры, которая необходима для осуществления алгоритмов апостериорного
логико-вероятностного вывода, эффективного поддержания глобальной непротиворечивости такой сети и визуализации АБС в виде графа. Проблема синтеза вторичной
структуры АБС по заданной первичной структуре является актуальной и нерешенной.
Обоснование актуальности исследований также содержит формальную сторону: тема настоящего диссертационного исследования ассоциирована с пунктом 35 ѕКогнитивные системы и технологии, . . . , искусственный интеллект, . . . , принятие решений
при многих критерияхї Программы фундаментальных научных исследований государственных академий наук на 20132020 годы (утверждена Распоряжением Правительства РФ от 03.12.2012 г. ќ 2237-р) в части ѕтеоретические и технологические основы, алгоритмическое обеспечение и программный инструментарий вероятностных
графических моделей, логико-вероятностных графических моделей, . . . ї.
Актуальность темы.
1 Машинное обучение одна из областей ИИ, связанная с разработкой моделей и алгоритмов, позволяющих вычислительной машине делать предсказания, основываясь на примерах
или предыдущем опыте (Alpaydin E. Introduction to Machine Learning. 2nd Ed. Cambridge, MS:
The MIT Press, 2010. 537 p.)
3
Степень разработанности темы. В работах А.Л. Тулупьева в качестве вторичной структуры АБС рассматриваются деревья смежности, для которых были предложены алгоритмы глобального логико-вероятностного вывода и эффективного поддержания глобальной непротиворечивости. Также в них был предложен подход к устранению отдельных простых циклов графа смежности, и, совместно с соавторами (в
первую очередь, с соискателем А.А. Фильченковым) подход к синтезу множества
минимальных графов смежности. А.В. Сироткин формализовал понятие магистральной связности как специфического свойства графов смежности. В.В. Опарин выдвинул
идею одного из вариантов синтеза минимального графа смежности, сводящуюся к использованию жадного алгоритма.
Исследованиями по выявлению и устранению цикличности гиперграфов занимались В.В. Быкова, C. Beeri, G. Dirac, R. Fagin, M. Goodman, D. Maier, A. Mendelzon, N.
Robertson, D. Rose, P. Seymour, R. Tarjan, J. Ullman, M. Yannakakis и многие другие.
Так, известны алгоритмы выявления цикличности гиперграфа и классы алгоритмов
ее устранения, которые мотивировали часть подходов к решению задач диссертационного исследования.
Объект исследования система глобальных структур АБС как специальных
графов и гиперграфов. Предмет исследования вторичная структура АБС, формализуемая как граф смежности, и машинное обучение этой структуры посредством
синтеза графов смежности.
Цель диссертационного исследования решить одну из проблем алгоритмизации глобального обучения АБС, а именно проблему синтеза вторичной структуры
АБС по ее первичной структуре. Достижение цели осуществляется за счет решения
совокупности следующих задач:
1) выявить критерии существования связной вторичной структуры и, отдельно,
ацикличной вторичной структуры над заданной первичной структурой АБС по косвенным признакам (т.е. не предполагающим непосредственное построение вторичной
структуры);
2) разработать методы преобразования первичной структуры АБС к структуре, над
которой существует ацикличная вторичная структура, и указать факторы, ограничивающие применимость таких методов;
3) выявить свойства минимальных по числу ребер графов смежности, которые могут выступать в качестве вторичной структуры АБС и существующие над произвольной первичной структурой, описать структуру такого множества и вывести формулы
для расчета мощности множества минимальных графов смежности и числа ребер такого графа;
4) разработать систему алгоритмов синтеза множества минимальных графов смежности, а также подмножеств этого множества, адаптированных к таким особенностям
алгоритмов логико-вероятностного вывода в теории АБС, как число шагов в пропагации свидетельства между узлами графа и распараллеливаемость этой пропагации;
5) реализовать описанные алгоритмы синтеза вторичной структуры АБС, а также
анализа и преобразования первичной структуры в прототипе комплекса программ для
вычислительных экспериментов.
Методология и методы исследования. Работа носит теоретический характер и
выполнена преимущественно в рамках теории конечных графов, в том числе теории
гиперграфов и ее приложений в информатике. Работа опирается на методологию дедуктивного и индуктивного обоснования утверждений в отношении специальным об-
4
разом формализованных объектов и сведения новых нерешенных задач к известным
задачам, уже получившим решение. Кроме того, используются объекты и методы алгебры, теории вероятностей и вероятностной логики, теории вычислительной сложности, комбинаторики, теории множеств, в частности, теории частично упорядоченных
множеств. В программно-технологической части исследования используются принципы структурного и объектно-ориентированного программирования и Java-технологии.
Научная новизна. Все результаты, выдвигаемые на защиту, являются новыми.
Предложены система алгоритмов синтеза глобальных структур АБС, алгоритмы
выявления существования связного графа смежности и ацикличного графа смежности над данной первичной структурой АБС, алгоритмы преобразования первичной
структуры к такой, над которой существует ацикличный граф смежности, алгоритмы синтеза множества минимальных графов смежности, а также синтеза особых его
подмножеств, доказана корректность указанных алгоритмов.
Дана оценка мощности множества минимальных графов смежности, доказана корректность матроидного представления семейства магистрально связных графов с заданным над ними отношением независимости, доказано совпадение множеств минимальных и нередуцируемых графов смежности. Предложено описание минимального
графа смежности, допускающее как синтез такого графа, так и синтез всего множества
таких графов, а также систематизация глобальных структур АБС на основе формализации через графы и гиперграфы. Доказано существование преобразования первичной
структуры АБС к первичной структуре, над которой существует дерево смежности,
как известными прежде, так и предложенными в диссертационном исследовании методами.
Разработаны программные компоненты, дополняющие существующий комплекс программ для работы с АБС и реализующие алгоритмы синтеза вторичной структуры
АБС, алгоритмы выявления существования дерева смежности над заданной первичной структурой АБС и ее преобразования к структуре допускающей, над которой существует дерево смежности.
Степень достоверности и апробация результатов. Достоверность полученных
в диссертационном исследовании результатов обоснована корректностью применения
методов соответствующих математических дисциплин. Существенным аргументом в
пользу достоверности является работоспособность прототипа комплекса программ, пополненного реализацией приведенных в теоретической части алгоритмах.
Результаты диссертационного исследования докладывались и обсуждались на следующих научных мероприятиях: 1) Научная сессия НИЯУ МИФИ-2011 (15 февраля 2011 г., Москва); 2) VI Междунар. науч.-практ. конф-я ѕИнтегрированные модели и мягкие вычисления в искусственном интеллектеї (1619 мая 2011 г., Коломна);
3) VII С.-Петерб. межрегион. конф-я ѕИнформационная безопасность регионов России (ИБРР-2011)ї (2628 октября 2011 г., С.-Петерб); 4) VI Междунар. науч.-практ.
конф-я ѕСовременные информационные технологии и IT-образованиеї (1214 декабря 2011 г., Москва); 5) Научная сессия НИЯУ МИФИ-2012 (30 января4 февраля 2012
г., Москва); 6) Всеросс. науч. конф-я по проблемам информатики СПИСОК-2012 (25
27 апреля 2012 г., С.-Петерб.); 7) VI Междунар. науч.-технич. конф-я молодых специалистов, аспирантов и студентов ѕМатематическое и компьютерное моделирование
естественнонаучных и социальных проблемї (2124 мая 2012 г., Пенза); 8) XV Междунар. конф-я по мягким вычислениям и измерениям (SCM'2012) (2527 июня 2012 г.,
С.-Петерб.); 9) 1-й Междунар. симпозиум ѕГибридные и синергетические интеллекту5
альные системы: теория и практикаї (29 июня 2 июля 2012 г., Калининград); 10) The
6th Russian Summer School in Information Retrieval (RuSSIR 2012) (August 610, 2012.
Yaroslavl, Russia); 11) 35-я конф-я молодых ученых и специалистов ИППИ РАН ѕИнформационные технологии и системыї (1925 августа 2012 г., Петрозаводск); 12) 5-я
росс. мультиконф-я по проблемам управления/конф-я ѕИнформационные технологии
в управлении2012ї (ИТУ2012) (911 октября 2012 г., С.-Петерб.); 13) Юбилейная
XIII С.-Петерб. междунар. конф-я ѕРегиональная информатика (РИ-2012)ї (2426 октября 2012 г., С.-Петерб.); 14) Междунар. (44-я Всеросс.) молодежная школа-конф-я
ѕСовременные проблемы информатики2013) (27 января 2 февраля 2013 г., Екатеринбург); 15) Научная сессия НИЯУ МИФИ-2013 (16 февраля 2013 г., Москва); 16)
Всеросс. науч. конф-я по проблемам информатики СПИСОК-2013 (2326 апреля 2013
г., С.-Петерб.). Кроме того, результаты диссертационного исследования докладывались на Санкт-Петербургском городском научном семинаре ѕИнформатика и компьютерные технологииї в 2013 году и на заседании Ученого совета СПИИРАН в 2013 году.
Исследования по тематике диссертации были поддержаны: 1) грантом РФФИ, проект ќ 09-01-00861-а ѕМетодология построения интеллектуальных систем поддержки
принятия решений на основе баз фрагментов знаний с вероятностной неопределенностьюї, 2) грантом РФФИ, проект ќ 12-01-00945-а ѕРазвитие теории алгебраических
байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностьюї, 3) грантом Правительства Санкт-Петербурга для
победителей конкурса грантов Санкт-Петербурга для студентов, аспирантов, молодых
ученых, молодых кандидатов наук 2010 г., ќ 2.1/0306/018, 4) грантом РФФИ, проект
12-01-31202 мол_а ѕРазвитие теории графов смежности для автоматического обучения баз знаний с неопределенностью на основе алгебраических байесовских сетейї,
5) грантом РФФИ, проект 12-01-16030-моб_з_рос ѕКосвенные признаки цикличности
вторичной структуры алгебраической байесовской сетиї для представления на научном мероприятии ѕ1-й Международный симпозиум "Гибридные и синергетические
интеллектуальные системы: теория и практика (ГиСИС'12)"ї. Соискатель является
руководителем проектов ќќ 35.
Теоретическая и практическая значимость исследования. Результаты диссертационного исследования развивают теоретическую и технологическую базу для
решения задач в системах поддержки принятия решений, в частности для представления и обработки неточной, неполной, нечисловой информации о соотношении вероятностей истинности утверждений, на основе которых принимаются решения, и для
комбинирования или агрегирования такой информации из источников, степени доверия к которым могут различаться или быть неизвестными. Кроме того, полученные
результаты в отношении минимальных по числу ребер графов смежности имеют теоретическую значимость для раздела теории графов, связанного с графами смежности.
Результаты исследований вошли в научные отчеты СПИИРАНа по следующим НИР:
ѕЛогико-вероятностный подход и его обобщения в моделировании, обработке и обучении баз фрагментов знаний с неопределенностью в интеллектуальных системахї,
шифр BNet-2008, номер государственной регистрации 01200852455, ѕМетодология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностьюї, номер государственной регистрации 01200963057, ѕРазвитие теории алгебраических байесовских сетей и родственных
им логико-вероятностных графических моделей систем знаний с неопределенностьюї,
номер государственной регистрации 01201259408.
6
Полученные результаты могут использоваться в учебном процессе для студентов,
специализирующихся в области информатики и родственных ей дисциплин. В частности, результаты были включены в программы спецкурса ѕТеория байесовских сетейї
и (частично) спецкурса ѕСУБД, интерфейс и интеллектуальные модели в комплексах
программї математико-механического факультета СПбГУ.
Публикации. По теме диссертации было сделано 58 публикаций и приравненных
к ним научных работ, из них 22 статьи (из которых 6 единоличных) в изданиях из
ѕПеречня рецензируемых научных журналов и изданий для опубликования основных
научных результатовї, утвержденного ВАК, 25 статей и докладов на научных конференциях (из которых 9 единоличных), 11 зарегистрированных программ ЭВМ и
алгоритмов (3 в РОСПАТЕНТе и 8 в ОФЭРНиО/ЦИТиСе). В дополнение к перечисленному материалы диссертационного исследования нашли отражение в 15 тезисах
научных конференций и 5 прошедших госрегистрацию в ЦИТиС научных отчетах.
Личный вклад А.А. Фильченкова в ключевых публикациях с соавторами кратко
характеризуется следующим образом: В [1] ему принадлежит доказательство теоремы
о матроидном представлении, а также теорема о совпадении множеств минимальных
и нередуцируемых графов смежности и доказательство ее корректность на основе теоремы о матроидном представлении; в [2] формулировки и доказательства утверждений и лемм о свойствах торакса; в [3] теорема о циклах в минимальных графах
смежности и ее доказательство; в [5] основные утверждения и леммы, их доказательство и доказательство теоремы о множестве минимальных графов смежности;
в [10] доказательство теоремы о совпадении множеств минимальных и нередуцируемых графов смежности, не основывающееся на корректности теоремы о матроидном
представлении; в [19] формулировка утверждений о связности первичной структуры
и их доказательства; в [8] описание задач глобального обучения АБС и подходов к
их решению; в [9, 12] алгоритмы выявления цикличности первичной структуры и
доказательства их корректности; в [6] формализация третичной структуры и описание ее свойств; в [11] методы устранения циклов и доказательство их корректности;
в [14] моделирование процесса распространения свидетельств по графу смежности
распространением свидетельств по родительскому графу над множеством непустых
сепараторов; в [16] новое, уточненное доказательство теоремы о циклах в минимальных графах смежности; в [18] формулировки основных утверждений и идеи
их доказательства, а также описание алгоритма и доказательство его корректности;
в [21] алгоритмы, а также доказательство их корректности; в [20] представление
первичной стурктуры АБС как гиперграфа и сведение задачи преобразования такой
структуры к ациклической к задачам, решаемым методами графовой декомпозиции.
Более подробно личный вклад А.А. Фильченкова в совместных публикациях и приравненных к ним работах описан в тексте диссертации.
Структура и объем диссертации. Диссертация состоит из введения, четырех
глав, заключения, списков используемой литературы и иллюстраций. Нумерация разделов, рисунков, формул, структурных элементов текста ведется отдельно для каждой
главы. Общий объем работы составляет 339 страниц. Список используемой литературы содержит 371 источник.
7
ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ
В автореферате изложены только основные определения, теоремы, утверждения и формулы. Нумерация теорем и утверждений самостоятельная и не зависит от нумерации указанных
элементов в тексте диссертации.
Во введении обосновывается актуальность диссертационного исследования, описываются степень разработанности его темы, предмет и объект исследования, цель и
задачи, методология и методы исследования, научная новизна и достоверность, апробация, а также теоретическая и практическая значимость исследования, раскрыт личный
вклад автора диссертационного исследования в совместных публикациях с другими
соавторами, приведена структура диссертации.
Первая глава состоит из четырех основных разделов, в первом из которых рассматриваются подходы к моделированию неопределенности через различные меры истинности: прежде всего рассмотрена вероятностная мера, затем описаны меры доверия
и правдоподобия, меры возможности и необходимости, и, наконец, внутренняя и внешняя меры. Последний аппарат, с одной стороны, глубоко проработан и имеет тесную
взаимосвязь с вероятностной мерой, а с другой обладает достаточной выразительной
мощностью, сопоставимой с другими рассмотренными аппаратами. Во втором разделе
описаны основные вероятностные графические модели (помимо прочих, БСД, скрытая
марковская модель, и АБС). В третьем разделе описаны области, в которых встречаются деревья смежности, а именно реляционные базы данных и задачи удовлетворения
ограничений, рассмотрена взаимосвязь деревьев смежности с гиперграфами и изложены методы графовой декомпозиции. Наконец, в четвертом разделе описаны подходы
к машинному обучению глобальной структуры БСД. В выводах по главе обоснованы
цель и задачи исследования.
Вторая глава содержит необходимые для дальнейшего изложения материалы, в
ней приводятся основы вероятностной логики в формализации Дж. Хальперна, Р. Фэйджина и Н. Меджиддо, теории конечных графов (в том числе гиперграфов), теории
упорядоченных множеств и теории АБС, основанной на результатах работ В.И. Городецкого, А.Л. Тулупьева и А.В. Сироткина.
Алфавит конечное множество атомарных пропозициональных формул (переменных) A = {x1 , . . . , xn }, которые для краткости будем называть атомами. Конъюнктом
над A называется конъюнкция некоторого поднабора (возможно, полного) положительно означенных атомов этого алфавита (но не их отрицаний): xi1 xi2 . . . xim , где
{i1 , . . . , im } ? {1, . . . , n}. Идеалом конъюнктов над A называется множество всех непустых конъюнктов, построенных над A. Идеал конъюнктов обозначается как C = C(A),
его мощность равна 2n ? 1.
Фрагмент знаний со скалярными оценками это пара вида (C(A), p), где p функция: p : C(A) ?? [0; 1]. Фрагмент знаний с интервальными оценками это
пара вида (C(A), p), где p функция: p : C(A) ?? {[a; b] | 0 ? a ? b ? 1}.
Задача локального априорного вывода состоит в том, чтобы на основе непротиворечивого фрагмента знаний построить оценки истинности пропозициональной формулы,
заданной над тем же алфавитом. Апостериорный вывод предполагает поступление
дополнительной информации, а именно некоторого свидетельства, т.е. новых ѕобуславливающихї данных. Выделяют две задачи апостериорного вывода. Первая задача
апостериорного вывода заключается в оценке вероятности истинности свидетельства
при уже заданных оценках истинности элементов фрагмента знаний. Вторая зада8
ча апостериорного вывода заключается в оценке условной вероятности истинности
элементов фрагмента знаний при предположении, что свидетельство истинно.
Через I обозначим некоторое конечное упорядоченное подмножество индексов элементов
алфавита
A, {Ai }i?I покрывающее семейство подалфавитов алфавита A,
(C(Ai ), pAi ) i?I семейство фрагментов знаний с интервальными оценками pAi , построенными над подалфавитами из {Ai }i?I . Фрагменты знаний в наборе называются
максимальными, если ни один элемент из {C(Ai )}i?I не содержит никакой другой.
Первичная структура АБС PSI = (C(Ai ), pAi )
это набор максимальных
i?I
фрагментов знаний (МФЗ). Вероятностной семантикой Sem(PSI ) первичной структуры PSI = {(CAi , pAi )}i?I с интервальными оценками называется семейство таких
вероятностных распределений pA , pA : C(A) ? [0; 1], значения которых для каждого
фрагмента знаний на его элементах попадают в соответствующие интервалы оценки
S
истинности: Sem (PSI ) = {pA |?c ? i?I C(Ai ) pA ? pAi (c)}.
Две первичные структуры называются стохастически эквивалентными, если их
вероятностные семантики совпадают. Объемлющим фрагментом знаний для данной
первичной структуры называется фрагмент знаний, построенный над всем алфавитом,
вероятностная семантика которого как первичной структуры совпадает с вероятностной семантикой исходной первичной структуры.
Виртуальное свидетельство представляет собой подфрагмент знаний, который
выделен из фрагмента знаний после пропагации и получения апостериорных оценок.
Пропагация свидетельства по дереву смежности предполагает пропагацию этого свидетельства в один из узлов сети, а затем распространение влияния этого свидетельства
по сети через формирование виртуальных свидетельств.
В третьей главе вводится система терминов для описания глобальных структур
АБС, сформулированы и доказаны теоретические результаты диссертационного исследования. Используется система терминов, составленная на основе [1, 5, 6, 11, 1416, 18,
19, 23, 24], ее основные элементы изложены ниже.
Нагруженный граф тройка hG, A, Wi, где G граф, A алфавит атомов, W функция нагрузки, заданная на множествах вершин и ребер G со значениями из 2A
(т.е. всевозможными подмножествами A). Нагрузкой подграфа нагруженного графа
T
называется пересечение нагрузок его вершин: W(G) = v?V(G) W(v). Сепаратором
двух вершин в нагруженном графе является пересечение их нагрузок: Sep (u, v) =
W (u) ? W (v). Множество всех непустых сепараторов обозначим Sep. Две вершины
называются сочлененными, если их сепаратор непуст.
Согласованный нагруженный граф такой нагруженный граф, что нагрузка любого ребра равна сепаратору концов этого ребра: ? (u, v) ? E W ((u, v)) = Sep (u, v) .
Граф МФЗ согласованный нагруженный граф, вершины которого соответствуют подалфавитам, над которыми построены идеалы соответствующих максимальных фрагментов знаний, а ребра в котором могут быть проведены только между сочлененными
вершинами. Магистральный путь (v1 , . . . , vn ) между двумя сочлененными вершинами v1 и vn , n ? 2 это путь, в котором нагрузка каждой вершины содержит сепаратор
его концов: ?i ? {2, . . . , n ? 1} Sep(v1 , vn ) ? W(vi ). Магистрально связный граф это
согласованный нагруженный граф, в котором каждая пара сочлененных вершин соединена магистральным путем.
Граф смежности магистрально связный граф МФЗ. Итак, граф смежности был
формализован как особый объект, который определен через тройку hG, A, Wi. Таким
9
Рис. 1. Вторичная структура АБС над ее первичной структурой
(сверху), соответствующая графу смежности (снизу).
Рис. 2. Первичная структура как набор вершин (слева) и как гиперграф (по центру), протоструктура (справа).
образом, формализуется первичная структура АБС: алфавит, над которым она построена, соответствует A, а подалфавиты, над которыми построены фрагменты знаний,
являются значениями W для соответствующих вершин. На рис. 1 приведен пример
вторичной структуры, и пример графа смежности, которому соответствует эта вторичная структура.
Рассмотрим вопросы выявления и устранения цикличности в первичной структуре,
которая представляется набором подалфавитов: PSI = {Ai }i?I , где I некоторое конечное множество индексов, заданных над подалфавитами алфавита A. Формализовать
первичную структуру можно как гиперграф hA, {Ai }i?I i, ребрами которого выступают
подалфавиты фрагментов знаний (рис. 2).
10 Связная первичная структура это первичная структура, над которой существует
связный граф смежности. Ацикличная первичная структура это первичная структура, над которой существует ацикличный граф смежности.
Протоструктура АБС с первичной структурой {Ai }i?I это граф, построенный
над алфавитом A, ребра которого соединяют два атома в том и только том случае, если они входят в какой-либо подалфавит Ai (рис. 2). Протоструктура является первичным графом гиперграфа, соответствующего первичной структуре АБС. Задачи выявления связности и ацикличности первичной структуры сведены к задачам выявления
связности и ацикличности гиперграфа, решаемым методами графовой декомпозиции:
первичная структура ациклична тогда и только тогда, когда ее протоструктура триангулярна, а ее ребра совпадают с вершинами максимальных клик протоструктуры.
Помимо этого предложны также иные способы выявления ацикличности первичной
структуры по косвенным признакам, основанные на оценке числа ребер в минимальном графе смежности и выявлении особых циклов в четвертичной структуре АБС (полусиблинговых небратских простых циклов ).
Рассмотрим вопрос о возможности преобразования первичной структуры к ацикличной. При таком преобразовании должна сохраняться ее вероятностная семантика.
(О единственности согласованной первичной структуры). Для заданной над семейством подалфавитов {Ai }i?I согласованной первичной структуры
I не существует отличной согласованной первичной структуры над тем
же набором подалфавитов, стохастически эквивалентной исходной.
Теорема 1.
PSI
Для двух минимальных гиперграфов H = hA, Ei и H 0 = hA, E 0 i будем говорить,
что H меньше H 0 , если для любого ребра из H можно указать ребро из E 0 , которое
совпадает с ним или содержит его: H ? H 0 ? ?e ? E ?e 0 ? E 0 : e ? e 0 .
(О построении семантически эквивалентных первичных структур
с интервальными оценками). Пусть задана согласованная первичная структура
I с интервальными оценками над семейством подалфавитов {Ai }i?I . Тогда
для любого множества индексов J, такого, что hA, {Ai }i?I i ? hA, {Aj }j?J i, можно
построить согласованную первичную структуру
J над {Aj }j?J , стохастически
эквивалентную исходной, причем единственным способом.
Теорема 2.
PSI
PSI
Таким образом, преобразования, переводящие гиперграф в больший гиперграф, и
только они в общем случае позволяют сохранить вероятностную семантику первичной
структуры АБС. Это позволяет свести задачу преобразования первичной структуры к
ацикличной к задаче преобразования гиперграфа к ацикличному. Помимо этого также предложены методы устранения цикличности первичной структуры за счет пополнения первичной структуры фрагментами знаний, устраняющими полусиблинговые
небратские простые циклы. Таким образом, задача синтеза вторичной структуры решена за счет преобразования первичной структуры к связной и ацикличной, а затем
построением дерева смежности одним из известных алгоритмов.
Однако предложенное решение обладает двумя недостатками. Во-первых, при преобразовании гиперграфа к ацикличному размер некоторых его ребер увеличивается.
Соответственно, при таком преобразовании первичной структуры к ацикличной может
увеличиться размер максимального фрагмента знаний, поэтому применимость подобного преобразования ограничена. Во-вторых, алгоритмы построения дерева смежности возвращают произвольное дерево смежности, тогда как особенности алгоритмов
11 глобального логико-вероятностного вывода, опирающихся на этот граф, выдвигают к
нему дополнительные требования, связанные с минимизацией времени работы алгоритма и числа шагов при распространении свидетельства от одного узла к другому.
Перечисленные затруднения решаются за счет рассмотрения более широкого, чем
деревья смежности, класса графов, а именно минимальных графов смежности.
Минимальный граф смежности граф смежности, число ребер в котором минимально среди всех графов смежности над той же первичной структурой. Минимальные
графы смежности, с одной стороны, существуют над любой первичной структурой, а,
с другой стороны, они минимальны и совпадают с деревьями смежности в случае
ацикличной первичной структуры.
Множество минимальных графов смежности совпадает с множеством деревьев смежности тогда и только тогда, когда связная первичная структура ациклична.
Теорема 3.
Максимальный граф смежности Gmax наибольший по числу ребер граф смежности. Сужение G ? U согласованного нагруженного графа G на непустой сепаратор
U это согласованный нагруженный граф, в который входят только те вершины и
ребра исходного графа G, нагрузки которых содержат или равны U. Через ? U будем
обозначать Gmax ? U.
Сильное сужение G U сужение G ? U, не содержащее ребра нагрузки U. Через
U будем обозначать Gmax U.
Жила нагрузки U граф, множество ребер которого состоит из |Conn( U)| ? 1
элементов, которые имеют нагрузку U и которые при добавлении в граф U делают
его связным, а множество ребер является множеством концов ребер, где Conn ( U) число компонент связности графа U. Пучок граф, построенный путем объединения
жил, выбранных по одной для каждого непустого сепаратора.
Теорема 4. (О множестве минимальных графов смежности). Множество минимальных графов смежности совпадает с множеством пучков.
Теорема о множестве минимальных графов смежности является ключевой, поскольку она конструктивно сопоставляет множеству минимальных графов смежности
декартово произведение множеств жил каждого непустого сепаратора.
Нередуцируемым графом смежности называется такой граф смежности, что при
удалении любого ребра он перестает быть магистрально связным.
(О множестве нередуцируемых графов смежности). Множество
нередуцируемых графов смежности совпадает с множеством минимальных графов смежности.
Теорема 5.
(О матроидном представлении множества магистрально связных
графов). Для первичной структуры, представленной набором подалфавитов V =
^ cmp = hV, Ecmp i над ней че{Ai }i?I , и полного согласованного нагруженного графа G
рез Ibbc обозначим множество всех независимых множеств, построенных над
V , где под независимостью множества A ? Ecmp будем понимать то, что со^ = hV, Ecmp \Ai магистрально связен. Тогда пара
гласованный лексический граф G
M = hEcmp , Ibbc i является матроидом.
Теорема 6.
Теорема о матроидном представлении множества магистрально связных графов
обосновывает возможность использования жадного алгоритма для синтеза некоторого
минимального графа смежности.
12 (О мощности множества минимальных графов смежности). Мощность множества минимальных графов смежности равна
Теорема 7.
nU
Y
!
v(Pi )
i=1
!nU ?2
v(Pi )
,
i=1
U разбивается на nU владений P1 , . . . , PnU .
где
nU
X
Теорема 8.
Число ребер в минимальном графе смежности равно
U?Sep
Conn (
U) ? |Sep| .
X
Основная идея алгоритмизации синтеза минимальных графов смежности состоит
в том, чтобы построить для сепараторов компоненты связности сильных сужений. На
основе множества множеств таких компонент можно синтезировать множество минимальных графов смежности и его подмножества (в том числе одноэлементные), строя
для каждого сепаратора множество или подмножество его жил и перебирая все кортежи по одному из каждого множества и объединяя их в графы.
При этом сложность работы алгоритмов синтеза подмножества минимальных графов смежности линейно зависит от числа элементов в таком подмножестве и полиномиально от числа сепараторов, для которых перебираются владения, поэтому
вместо рассмотрения всего множества непустых сепараторов предлагается рассматривать только стереосепараторы сепараторы, для которых число жил больше одной,
особым образом учитывая остальные сепараторы. Введем их классификацию.
Бисепаратор сепаратор, сужение на который состоит из двух вершин. Обязательное ребро ребро, являющееся жилой бисепаратора.
Утверждение 1.
Обязательное ребро входит в каждый минимальный граф смеж-
ности.
Граф обязательных ребер граф на вершинах первичной структуры, состоящий
только из обязательных ребер. Стереосепаратор сепаратор, которому соответствует более одной жилы. Основной алгоритмов синтеза подмножеств минимальных графов смежности является синтез по заданному набору нагрузок Workloads трех других
множеств: Stereoseparators множества стереосепараторов, Stereoholdings множества владений стереосепараторов и NeccessaryEdges обязательных ребер, по которому строится подмножество минимальных графов смежности.
Предложено шесть алгоритмов синтеза такого множества, работа которых сводится
к следующим шагам (которые в некоторых алгоритмах могут быть объединены в один
или выполняться в ином порядке):
1) построить множество непустых сепараторов Separators;
2) для каждого элемента Separators построить вершины, попадающие в сужение на
него; ребра тех, в которых ровно две вершины, добавить в NeccessaryEdges и исключить
из рассмотрения;
3) для каждого элемента Separators построить владения этого сепаратора, если их
больше одного, то добавить сепаратор к Stereoseparators, а владения к Stereoholdings.
Предложены также модификации этого метода, которые состоят в том, чтобы строить сужения минимальных графов смежности на сепараторы не перебором всех вершин и их сепараторов, но перебором вершин и сепа??аторов, попавших в сужение на
сепараторародителя. Это, однако, предполагает построение родительского графа 13 т.е. третичной структуры. Другая модификация состоит в том, чтобы выявлять владения на основе полусиблингового графа для соответствующего сепаратора. Собственная вершина сепаратора U такая вершина v, что для некоторой другой вершины u
Sep(v, u) = U. Еще одно улучшение связано с построением только множества собственных вершин вместо построения сужения.
Оценка сложности таких алгоритмов лежит в классе O(mw2 + msw + sw2 + ms2 ),
где w число фрагментов знаний в первичной структуре, m максимальное число
атомов во фрагменте знаний, а s число непустых сепараторов.
Локально звездчатым графом смежности будем называть такой минимальный
граф смежности, что любая его жила является звездой. В диссертации локально звездчатые графы смежности рассматриваются как одно из подмножеств минимальных
графов смежности, которое помогает искать минимальные графы смежности с минимальным диаметром эффективнее, чем полным перебором.
Рандомизированный алгоритм синтеза минимальных графов смежности строит минимальный граф смежности с ненулевой вероятностью.
Алгоритм выявления ацикличности первичной структуры на основе оценки числа
ребер в минимальном графе смежности состоит из следующих шагов:
1) выявление связности первичной структуры;
2) построение множества непустых сепараторов Separators;
3) построение владений для каждого сепаратора;
4) проверка того, что число владений всех непустых сепараторов, уменьшенному на
число непустых сепараторов, равно числу фрагментов знаний, уменьшенному на 1.
Алгоритм выявления ацикличности первичной структуры на основе выявления полусиблинговых небратских простых циклов состоит из следующих шагов:
1) построение множества Separators;
2) построение родительского графа над замкнутым сверху множеством непустых
сепараторов;
3) построение для каждого сепаратора полусиблингового графа;
4) поиск в каждом полусиблинговом графе полусиблинговых небратских простых
циклов.
В четвертой главе описываются основные моменты программной реализации прототипа комплекса программ для вычислительных экспериментов. Описана структура
комплекса программ, разделенного на четыре основных пакета, один из которых содержит классы и методы для выявления и устранения цикличности первичной структуры, другой для синтеза множества минимальных графов смежности и его подмножеств, третий для сохранения и загрузки полученных результатов и четвертый
содержит панель графического пользовательского интерфейса.
Приведено описание программной реализации основных алгоритмов синтеза множества минимальных графов смежности. Приведено руководство пользователя для
работы с основными функциями прототипа программного комплекса, реализующего
приведенные в работе алгоритмы, а также даны иллюстративные примеры работы с
комплексом. Разработанный прототип содержит более 3600 строк программного кода.
Заключение содержит основные результаты и выводы по диссертационной работе.
ЗАКЛЮЧЕНИЕ
Основные результаты диссертационного исследования:
14 1) выявлены критерии существования ацикличного графа смежности над заданной
первичной структурой, основанные на оценке числа ребер в минимальном графе смежности и на выявлении существования полусиблинговых небратских простых циклов в
четвертичной структуре АБС; предложены и обоснованы методы выявления связности и (отдельно) ацикличности первичной структуры АБС через выявление связности
и ацикличности соответствующего ей гиперграфа (за счет сведения исходных задач к
задачам, решаемыми методами графовой декомпозиции, на основе введенной формализации первичной структуры);
2) предложены и обоснованы методы устранения цикличности графа смежности за
счет пополнения первичной структуры фрагментами знаний, устраняющих полусиблинговые небратские простые циклы; предложены и обоснованы методы преобразования первичной структуры АБС к ацикличной структуре с той же вероятностной
семантикой через сведение соответствующего ей гиперграфа к ацикличному (за счет
сведения исходной задачи к задачам, решаемыми методами графовой декомпозиции,
на основе введенной формализации первичной структуры);
3) сформулирован комплекс теорем, сопоставляющих множеству минимальных графов смежности декартово произведение множеств жил каждого непустого сепаратора,
выражающих мощность этого множества, его эквивалентность множеству нередуцируемых графов смежности, число ребер в минимальном графе смежности, указанные
теоремы доказаны; составлена систематизация глобальных структур АБС на основе
графового и гиперграфового представления;
4) построена система алгоритмов синтеза множества минимальных графов смежности по первичной структуре АБС, обеспечивающая синтез множества минимальных
графов смежности, множества звездчатых графов смежности, а также рандомизированный синтез реализации случайного минимального графа смежности (с ненулевой
вероятностью каждой возможной реализации);
5) реализованы в виде компонент прототипа комплекса программ алгоритмы выявления существования связной и (отдельно) ацикличной вторичной структуры над
заданной первичной структурой АБС, преобразования первичной структуры АБС к
структуре, допускающей такое построение, а также система алгоритмов синтеза глобальных структур АБС.
Перспективными направлениями дальнейшего исследования являются направления, связанные с оптимизацией поиска минимальных графов смежности, оптимизирующих численных характеристики работы алгоритмов логико-вероятностного вывода,
а также со сравнением работы предложенных алгоритмов для реальных примеров
алгебаических байесовских сетей.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
Статьи, опубликованные в изданиях из ѕПеречня рецензируемых научных
журналов и изданий для опубликования основных научных результатовї
1.
Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический
вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. C. 7376.
2. Фильченков А.А., Тулупьев А.Л. Понятие торакса в применении к исследованию графов
смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 1 (16).
С. 186205.
Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В.
15 3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 2 (17). С. 151173.
Фильченков A.A. Алгоритмы построения третичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 2(17). С. 197218.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Структурный анализ клик максимальных графов смежности алгебраических байесовских сетей // Вестн. Тверск. гос. ун-та.
Сер.: Прикладная математика. 2011. ќ20. С. 139151.
Фильченков А.А., Тулупьев А.Л. Третичная структура алгебраической байесовской сети
// Труды СПИИРАН. 2011. Вып. 3 (18). С. 164187.
Фильченков A.A. Алгоритмы построения элементов третичной полиструктуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 3 (18). С. 237266.
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. ќ 11, т. 9. С. 5761.
Фильченков А.А., Тулупьев А.Л. Алгоритм выявления ацикличности первичной структуры алгебраической байесовской сети по ее четвертичной структуре // Труды СПИИРАН.
2011. Вып. 4(19). С. 128145.
Фильченков А.А., Тулупьев А.Л. Совпадение множеств минимальных и нередуцируемых
графов смежности над первичной структурой алгебраической байесовской сети // Вестник
Санкт-Петербургского государственного университета. Серия 1. Математика. Механика.
Астрономия. 2012. Вып. 2. С. 6978.
Фильченков А.А., Фроленков К.В., Тулупьев А.Л. Устранение циклов во вторичной структуре алгебраической байесовской сети на основе анализа ее четвертичной структуры //
Труды СПИИРАН. 2012. Вып. 2(21). С. 143156.
Фильченков А.А. Тулупьев А.Л. Алгоритм выявления ацикличности первичной структуры алгебраической байесовской сети на основе оценки числа ребер в минимальном графе
смежности // Труды СПИИРАН. 2012. Вып. 3(22). С. 205223.
Фильченков А.А. Меры истинности и вероятностные графические модели для представления знаний с неопределенностью // Труды СПИИРАН. 2012. Вып. 4(23). С. 254295.
Фроленков К.В., Фильченков А.А., Тулупьев А.Л. Апостериорный вывод в третичной
полиструктуре алгебраических байесовских сетей // Труды СПИИРАН. 2012. Вып. 4(23).
С. 343356.
Фильченков А.А. Иерархия глобальных структур алгебраической байесовской сети как
система графов и гиперграфов // Научно-технический вестник информационных технологий, механики и оптики. 2013. Вып. 1(83). С. 7580.
Фроленков К.В., Фильченков А.А., Тулупьев А.Л. Сиблинговый критерий цикличности
минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 2(25). С. 190203.
Фильченков А.А. Субоптимальная звездчатая структура алгебраической байесовской сети
// Информационно-управляющие системы. 2013. Вып. 2. С. 1317.
Фильченков А.А., Мусина В.Ф., Тулупьев А.Л. Алгоритм рандомизированного синтеза
минимального графа смежности // Труды СПИИРАН. 2013. Вып. 2(35). С. 221-234.
Фильченков А.А., Тулупьев А.Л. Связность и ацикличность первичной структуры алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2013. Вып. 1. C. 110119.
Вяткин А.В., Фильченков А.А., Тулупьев А.Л., Мусина В.Ф., Фроленков К.В. Подходы к устранению цикличности первичной структуры алгебраической байесовской сети //
Труды СПИИРАН. 2013. Вып. 3(26). С. 216233.
Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Система алгоритмов
синтеза подмножеств минимальных графов смежности // Труды СПИИРАН. 2013. Вып.
4(27). С. 200244.
Фильченков А.А. Преобразование первичной структуры алгебраической байесовской сети
к ациклической с сохранением вероятностной семантики // Труды СПИИРАН. Вып. 7(30).
С. 141153.
Фильченков А.А., Тулупьев А.Л.
16 Научные статьи и доклады, опубликованные в других изданиях
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
Структурный анализ систем минимальных графов смежности
// Труды СПИИРАН. 2009. Вып. 11. СПб. Наука, 2009. С. 104127.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). C. 97118.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи
самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1(12). C. 119133.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2(13). С. 87
105.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи
клик владений // Труды СПИИРАН. 2010. Вып. 2(13). С. 6786.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей //
Труды СПИИРАН. 2010. Вып. 3(14). С. 132149.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи
самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3(14). С. 150169.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Мощность множества минимальных графов
смежности // Труды СПИИРАН. 2010. Вып. 4(15). С. 136161.
Фильченков А.А. Алгоритм построения множества минимальных графов смежности при помощи
клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4(15). С. 193212.
Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Минимальные графы смежности алгебраической
байесовской сети: формализация основ синтеза и автоматического обучения // Нечеткие системы и мягкие вычисления. Научный журнал Российской ассоциации нечетких систем и мягких
вычислений. 2011. Том 6, ќ 2. С. 145163.
Filchenkov A.A., Tulupyev A.L. Coincidence of the Sets of Minimal and Irreducible Join Graphs over
Primary Structure of Algebraic Bayesian Networks // Vestnik St. Petersburg University. Mathematics.
2012. Vol. 45, no. 2. Allerton Press, Inc.: 2012. P. 106113.
Тулупьев А.Л., Фильченков А.А., Вальтман Н.А., Мусина В.Ф. Состояние и перспективы развития
подходов к автоматическому обучению алгебраических байесовских сетей // VIя Международная научно-практическая конф-я ѕИнтегрированные модели и мягкие вычисления в искусственном интеллектеї. (1619 мая 2011 г., Коломна.) Сборник научных трудов. Т. 1. М.: Физмат, 2011.
С. 10011012.
Фильченков А.А. Анализ вторичной структуры алгебраической байесовской сети // VIя Международная научно-практическая конф-я ѕИнтегрированные модели и мягкие вычисления в
искусственном интеллектеї. (1619 мая 2011 г., Коломна.) Сборник научных трудов. Т. 1. М.:
Физмат, 2011. С. 10131024.
Тулупьев А.Л., Фильченков А.А. Иерархия глобальных структур в задачах автоматического обучения алгебраических байесовских сетей // VI Международная научно-практическая конф-я
ѕСовременные информационные технологии и IT-образованиеї. (1214 декабря 2011 г., Москва.)
Сборник научных трудов. М. 2011. С. 490496.
Фильченков А.А. Алгоритм выявления цикличности первичной структуры алгебраической байесовской сети // VI Международная научно-практическая конф-я ѕСовременные информационные технологии и IT-образованиеї. (1214 декабря 2011 г., Москва.) Сборник научных трудов.
М. 2011. С. 496504.
Фильченков А.А., Тулупьев А.Л. Вычисление мощности множества минимальных графов смежности // СПИСОК-2012: Материалы всероссийской научной конф-и по проблемам информатики
(2527 апреля 2012 г., Санкт-Петербург). СПб.: ВВМ, 2012. С. 378384.
Фильченков А.А. Междисциплинарные связи в преподавании теории алгебраических байесовских
сетей // VI Международная научно-практическая конф-я молодых специалистов, аспирантов и
студентов ѕМатематическое и компьютерное моделирование естественнонаучных и социальных
проблемї. (2124 мая 2012 г., Пенза.) Сборник статей. Пенза: Приволжский дом знаний. 2012 г.
С. 182185.
Фильченков А.А. Визуальная инструментальная платформа для работы с алгебраическими байесовскими сетями // XV Международная конф-я по мягким вычислениям и измерениям SCM'12.
(2527 июня 2012 г., Санкт-Петербург.) Сборник докладов. Т. 1. СПб: ЛЭТИ. 2012. С. 195199.
Фильченков А.А., Фроленков К.В., Тулупьев А.Л. Программная реализация выявления цикличности алгебраической байесовской сети по косвенным признакам // XV Международная конф-я
по мягким вычислениям и измерениям SCM'12. (2527 июня 2012 г., Санкт-Петербург.) Сборник
докладов. Т. 1. СПб: ЛЭТИ. 2012. С. 200204.
Фильченков А.А., Фроленков К.В., Тулупьев А.Л. Представление и визуализация вторичной структуры алгебраических байесовских сетей в комплексе программ // XV Международная конф-я
по мягким вычислениям и измерениям SCM'12. (2527 июня 2012 г., Санкт-Петербург.) Сборник
докладов. Т. 1. СПб: ЛЭТИ. 2012. С. 210214.
Фильченков А.А., Тулупьев А.Л. Косвенные признаки цикличности вторичной структуры алгебраической байесовской сети // ѕГибридные и синергетические интеллектуальные системы:
теория и практикаї (29 июня 2 июля 2012 г., Калининград). Материалы 1го международного
симпозиума. Т. 2. Калининград: БФУ им. Канта.2012. С. 918.
Фроленков К.В., Фильченков А.А. Методы устранения циклов вторичной структуры алгебраической байесовской сети // ѕГибридные и синергетические интеллектуальные системы: теория и
Фильченков А.А., Тулупьев А.Л.
17 практикаї (29 июня 2 июля 2012 г., Калининград). Материалы 1го международного симпозиума. Т. 2. Калининград: БФУ им. Канта.2012. С. 282292.
45. Фильченков А.А. Алгебраическая байесовская сеть как основа для медицинской диагностической
модели // ѕМатематическое и компьютерное моделирование в биологии и химии. Перспективы
развитияї. (2830 мая 2012 г., Казань). Сборник трудов I Международной интернет-конф-и.
Казань.: Из-во ѕКазанский университетї. 2012.С. 162166.
46. Фильченков А.А., Сироткин А.В. Выявление ацикличности вторичной структуры алгебраической
байесовской сети на основе подсчета числа ее ребер // 35-я конф-я молодых ученых и специалистов ИППИ РАН ѕИнформационные технологии и системы 2012ї. (1925 августа 2012 г.,
Петрозаводск). Сборник трудов. С. 2428.
47. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Управление глобальной структурой знаний в
интеллектуальных системах, основанных на алгебраических байесовских сетях // Материалы
конф-и ѕИнформационные технологии в управленииї (ИТУ2012) (911 октября 2012 г., СанктПетербург). СПб.: ОАО ѕКонцерн ѕЦНИИ ѕЭлектроприборї. 2012. С. 2533.
Зарегистрированные программы для ЭВМ и алгоритмы
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
Программа для поддержки синтеза наборов
бинарных последовательностей без поглощающих элементов при формировании алгебраической байесовской сети Algebraic Bayesian Networks Primary Structure Rener, Version 01 for Java
(AlgBNPSRj.v.01) // Свид. о гос. рег. прогр. для ЭВМ. Рег. ќ 2010614270(30.06.2010). РОСПАТЕНТ // Бюлл. ѕПрогр. для ЭВМ, БД, топол. инт. микросх.ї. 2010. ќ3. С. 456.
Тулупьев А.Л., Фильченков А.А., Сироткин А.В. Программа для визуализации операций по формированию первичной структуры алгебраической байесовской сети Algebraic Bayesian Networks
Primary Structure Visualizer, Version 01 forJava (AlgBNPSVj.v.01) // Свид. о гос. рег. прогр. для
ЭВМ. Рег. ќ 2010614268(30.06.2010). РОСПАТЕНТ // Бюлл. ѕПрогр. для ЭВМ, БД, топол. инт.
микросх.ї. 2010. ќ3. С. 455.
Тулупьев А.Л., Фильченков А.А., Сироткин А.В. Программа для синтеза семейства минимальных графов смежности Algebraic Bayesian Networks Secondary Structures Generator, Version 01
for Java (AlgBNSSGj.v.01) // Свид. о гос. рег. прогр. для ЭВМ. Рег. ќ 2010614269(30.06.2010).
РОСПАТЕНТ // Бюлл. ѕПрогр. для ЭВМ, БД, топол. инт. микросх.ї. 2010. ќ3. С. 455456.
Тулупьев А.Л., Фильченков А.А., Сироткин А.В. Система для построения и визуализации семейства минимальных вторичных структур алгебраической байесовской сети, соответствующих ее
первичной структуре (свидетельство) // Свид. о рег. эл. ресурса, (ОФЭРНиО ИИО ГАН РАО)
ќ 15769 от 20.05.2010. Бюлл. ѕХроники объед. фонда эл. ресурсов ѕНаука и образованиеї 2010.
ќ5. С. 27.
Тулупьев А.Л., Великодная О.И., Фильченков А.А. Программа для поддержки синтеза наборов
фрагментов знаний с согласованными оценками вероятностей для формирования алгебраической байесовской сети (свидетельство). Гос. рег. ќ 50201151353 от 27.10.2011 (ЦИТиС). Свид. о
рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) ќ 17531 от 26.10.2011. Бюлл. ѕХроники объед.
фонда эл. ресурсов ѕНаука и образованиеї. 2011. ќ 10(29). С. 20.
Тулупьев А.Л., Пинский М.Я., Фильченков А.А. База данных для хранения алгебраических байесовских сетей (свидетельство). Гос. рег. ќ 50201151352 от 27.10.2011 (ЦИТиС). Свид. о рег. эл.
ресурса, (ОФЭРНиО ИНИМ ГАН РАО) ќ 17532 от 26.10.2011. Бюлл. ѕХроники объед. фонда
эл. ресурсов ѕНаука и образованиеї. 2011. ќ 10(29). С. 2021.
Тулупьев А.Л., Пинский М.Я., Фильченков А.А. Графический web-интерфейс пользователя
для хранения алгебраических байесовских сетей (свидетельство). Гос. рег. ќ 50201151351 от
27.10.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) ќ 17533 от
26.10.2011. Бюлл. ѕХроники объед. фонда эл. ресурсов ѕНаука и образованиеї. 2011. ќ 10(29).
С. 21.
Фильченков А.А., Тулупьев А.Л. Алгоритм построения родительского графа снизувверх. Гос.
рег. ќ 50201151517 от 07.12.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН
РАО) ќ 17660 от 07.12.2011. Бюлл. ѕХроники объед. фонда эл. ресурсов ѕНаука и образованиеї.
2011. ќ 12(31). С. 7.
Фильченков А.А., Тулупьев А.Л. Алгоритм выявления ацикличности первичной структуры алгебраических байесовских сетей на основе анализа их четвертичной структуры. Гос. рег. ќ
50201151516 от 07.12.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО)
ќ 17661 от 07.12.2011. Бюлл. ѕХроники объед. фонда эл. ресурсов ѕНаука и образованиеї. 2011.
ќ 12(31). С. 7.
Фильченков А.А., Тулупьев А.Л. Алгоритм построения родительского графа при помощи потомков. Гос. рег. ќ 50201151515 от 07.12.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ
ГАН РАО) ќ 17662 от 07.12.2011. Бюлл. ѕХроники объед. фонда эл. ресурсов ѕНаука и образованиеї. 2011. ќ 12(31). С. 78.
Тулупьев А.Л., Фильченков А.А., Алексеев А.М. Генератор HTML-таблиц по обобщенному правилу modusponens в вероятностной логике (скалярные ограничения). Гос. рег. ќ50201250632
от 16.05.2012 (ЦИТиС) Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) ќ 18300 от
16.05.2012. Бюлл. ѕХроники объед. фонда эл. ресурсов ѕНаука и образованиеї. 2012. ќ 5(36).
С. 18.
Тулупьев А.Л., Фильченков А.А., Сироткин А.В.
18 ?ния, теоремы, утверждения и формулы. Нумерация теорем и утверждений самостоятельная и не зависит от нумерации указанных
элементов в тексте диссертации.
Во введении обосновывается актуальность диссертационного исследования, описываются степень разработанности его темы, предмет и объект исследования, цель и
задачи, методология и методы исследования, научная новизна и достоверность, апробация, а также теоретическая и практическая значимость исследования, раскрыт личный
вклад автора диссертационного исследования в совместных публикациях с другими
соавторами, приведена структура диссертации.
Первая глава состоит из четырех основных разделов, в первом из которых рассматриваются подходы к моделированию неопределенности через различные меры истинности: прежде всего рассмотрена вероятностная мера, затем описаны меры доверия
и правдоподобия, меры возможности и необходимости, и, наконец, внутренняя и внешняя меры. Последний аппарат, с одной стороны, глубоко проработан и имеет тесную
взаимосвязь с вероятностной мерой, а с другой обладает достаточной выразительной
мощностью, сопоставимой с другими рассмотренными аппаратами. Во втором разделе
описаны основные вероятностные графические модели (помимо прочих, БСД, скрытая
марковская модель, и АБС). В третьем разделе описаны области, в которых встречаются деревья смежности, а именно реляционные базы данных и задачи удовлетворения
ограничений, рассмотрена взаимосвязь деревьев смежности с гиперграфами и изложены методы графовой декомпозиции. Наконец, в четвертом разделе описаны подходы
к машинному обучению глобальной структуры БСД. В выводах по главе обоснованы
цель и задачи исследования.
Вторая глава содержит необходимые для дальнейшего изложения материалы, в
ней приводятся основы вероятностной логики в формализации Дж. Хальперна, Р. Фэйджина и Н. Меджиддо, теории конечных графов (в том числе гиперграфов), теории
упорядоченных множеств и теории АБС, основанной на результатах работ В.И. Городецкого, А.Л. Тулупьева и А.В. Сироткина.
Алфавит конечное множество атомарных пропозициональных формул (переменных) A = {x1 , . . . , xn }, которые для краткости будем называть атомами. Конъюнктом
над A называется конъюнкция некоторого поднабора (возможно, полного) положительно означенных атомов этого алфавита (но не их отрицаний): xi1 xi2 . . . xim , где
{i1 , . . . , im } ? {1, . . . , n}. Идеалом конъюнктов над A называется множество всех непустых конъюнктов, построенных над A. Идеал конъюнктов обозначается как C = C(A),
его мощность равна 2n ? 1.
Фрагмент знаний со скалярными оценками это пара вида (C(A), p), где p функция: p : C(A) ?? [0; 1]. Фрагмент знаний с интервальными оценками это
пара вида (C(A), p), где p функция: p : C(A) ?? {[a; b] | 0 ? a ? b ? 1}.
Задача локального априорного вывода состоит в том, чтобы на основе непротиворечивого фрагмента знаний построить оценки истинности пропозициональной формулы,
заданной над тем же алфавитом. Апостериорный вывод предполагает поступление
дополнительной информации, а именно некоторого свидетельства, т.е. новых ѕобуславливающихї данных. Выделяют две задачи апостериорного вывода. Первая задача
апостериорного вывода заключается в оценке вероятности истинности свидетельства
при уже заданных оценках истинности элементов фрагмента знаний. Вторая зада8
ча апостериорного вывода заключается в оценке условной вероятности истинности
элементов фрагмента знаний при предположении, что свидетельство истинно.
Через I обозначим некоторое конечное упорядоченное подмножество индексов элементов
алфавита
A, {Ai }i?I покрывающее семейство подалфавитов алфавита A,
(C(Ai ), pAi ) i?I семейство фрагментов знаний с интервальными оценками pAi , построенными над подалфавитами из {Ai }i?I . Фрагменты знаний в наборе называются
максимальными, если ни один элемент из {C(Ai )}i?I не содержит никакой другой.
Первичная структура АБС PSI = (C(Ai ), pAi )
это набор максимальных
i?I
фрагментов знаний (МФЗ). Вероятностной семантикой Sem(PSI ) первичной структуры PSI = {(CAi , pAi )}i?I с интервальными оценками называется семейство таких
вероятностных распределений pA , pA : C(A) ? [0; 1], значения которых для каждого
фрагмента знаний на его элементах попадают в соответствующие интервалы оценки
S
истинности: Sem (PSI ) = {pA |?c ? i?I C(Ai ) pA ? pAi (c)}.
Две первичные структуры называются стохастически эквивалентными, если их
вероятностные семантики совпадают. Объемлющим фрагментом знаний для данной
первичной структуры называется фрагмент знаний, построенный над всем алфавитом,
вероятностная семантика которого как первичной структуры совпадает с вероятностной семантикой исходной первичной структуры.
Виртуальное свидетельство представляет собой подфрагмент знаний, который
выделен из фрагмента знаний после пропагации и получения апостериорных оценок.
Пропагация свидетельства по дереву смежности предполагает пропагацию этого свидетельства в один из узлов сети, а затем распространение влияния этого свидетельства
по сети через формирование виртуальных свидетельств.
В третьей главе вводится система терминов для описания глобальных структур
АБС, сформулированы и доказаны теоретические результаты диссертационного исследования. Используется система терминов, составленная на основе [1, 5, 6, 11, 1416, 18,
19, 23, 24], ее основные элементы изложены ниже.
Нагруженный граф тройка hG, A, Wi, где G граф, A алфавит атомов, W функция нагрузки, заданная на множествах вершин и ребер G со значениями из 2A
(т.е. всевозможными подмножествами A). Нагрузкой подграфа нагруженного графа
T
называется пересечение нагрузок его вершин: W(G) = v?V(G) W(v). Сепаратором
двух вершин в нагруженном графе является пересечение их нагрузок: Sep (u, v) =
W (u) ? W (v). Множество всех непустых сепараторов обозначим Sep. Две вершины
называются сочлененными, если их сепаратор непуст.
Согласованный нагруженный граф такой нагруженный граф, что нагрузка любого ребра равна сепаратору концов этого ребра: ? (u, v) ? E W ((u, v)) = Sep (u, v) .
Граф МФЗ согласованный нагруженный граф, вершины которого соответствуют подалфавитам, над которыми построены идеалы соответствующих максимальных фрагментов знаний, а ребра в котором могут быть проведены только между сочлененными
вершинами. Магистральный путь (v1 , . . . , vn ) между двумя сочлененными вершинами v1 и vn , n ? 2 это путь, в котором нагрузка каждой вершины содержит сепаратор
его концов: ?i ? {2, . . . , n ? 1} Sep(v1 , vn ) ? W(vi ). Магистрально связный граф это
согласованный нагруженный граф, в котором каждая пара сочлененных вершин соединена магистральным путем.
Граф смежности магистрально связный граф МФЗ. Итак, граф смежности был
формализован как особый объект, который определен через тройку hG, A, Wi. Таким
9
Рис. 1. Вторичная структура АБС над ее первичной структурой
(сверху), соответствующая графу смежности (снизу).
Рис. 2. Первичная структура как набор вершин (слева) и как гиперграф (по центру), протоструктура (справа).
образом, формализуется первичная структура АБС: алфавит, над которым она построена, соответствует A, а подалфавиты, над которыми построены фрагменты знаний,
являются значениями W для соответствующих вершин. На рис. 1 приведен пример
вторичной структуры, и пример графа смежности, которому соответствует эта вторичная структура.
Рассмотрим вопросы выявления и устранения цикличности в первичной структуре,
которая представляется набором подалфавитов: PSI = {Ai }i?I , где I некоторое конечное множество индексов, заданных над подалфавитами алфавита A. Формализовать
первичную структуру можно как гиперграф hA, {Ai }i?I i, ребрами которого выступают
подалфавиты фрагментов знаний (рис. 2).
10 Связная первичная структура это первичная структура, над которой существует
связный граф смежности. Ацикличная первичная структура это первичная структура, над которой существует ацикличный граф смежности.
Протоструктура АБС с первичной структурой {Ai }i?I это граф, построенный
над алфавитом A, ребра которого соединяют два атома в том и только том случае, если они входят в какой-либо подалфавит Ai (рис. 2). Протоструктура является первичным графом гиперграфа, соответствующего первичной структуре АБС. Задачи выявления связности и ацикличности первичной структуры сведены к задачам выявления
связности и ацикличности гиперграфа, решаемым методами графовой декомпозиции:
первичная структура ациклична тогда и только тогда, когда ее протоструктура триангулярна, а ее ребра совпадают с вершинами максимальных клик протоструктуры.
Помимо этого предложны также иные способы выявления ацикличности первичной
структуры по косвенным признакам, основанные на оценке числа ребер в минимальном графе смежности и выявлении особых циклов в четвертичной структуре АБС (полусиблинговых небратских простых циклов ).
Рассмотрим вопрос о возможности преобразования первичной структуры к ацикличной. При таком преобразовании должна сохраняться ее вероятностная семантика.
(О единственности согласованной первичной структуры). Для заданной над семейством подалфавитов {Ai }i?I согласованной первичной структуры
I не существует отличной согласованной первичной структуры над тем
же набором подалфавитов, стохастически эквивалентной исходной.
Теорема 1.
PSI
Для двух минимальных гиперграфов H = hA, Ei и H 0 = hA, E 0 i будем говорить,
что H меньше H 0 , если для любого ребра из H можно указать ребро из E 0 , которое
совпадает с ним или содержит его: H ? H 0 ? ?e ? E ?e 0 ? E 0 : e ? e 0 .
(О построении семантически эквивалентных первичных структур
с интервальными оценками). Пусть задана согласованная первичная структура
I с интервальными оценками над семейством подалфавитов {Ai }i?I . Тогда
для любого множества индексов J, такого, что hA, {Ai }i?I i ? hA, {Aj }j?J i, можно
построить согласованную первичную структуру
J над {Aj }j?J , стохастически
эквивалентную исходной, причем единственным способом.
Теорема 2.
PSI
PSI
Таким образом, преобразования, переводящие гиперграф в больший гиперграф, и
только они в общем случае позволяют сохранить вероятностную семантику первичной
структуры АБС. Это позволяет свести задачу преобразования первичной структуры к
ацикличной к задаче преобразования гиперграфа к ацикличному. Помимо этого также предложены методы устранения цикличности первичной структуры за счет пополнения первичной структуры фрагментами знаний, устраняющими полусиблинговые
небратские простые циклы. Таким образом, задача синтеза вторичной структуры решена за счет преобразования первичной структуры к связной и ацикличной, а затем
построением дерева смежности одним из известных алгоритмов.
Однако предложенное решение обладает двумя недостатками. Во-первых, при преобразовании гиперграфа к ацикличному размер некоторых его ребер увеличивается.
Соответственно, при таком преобразовании первичной структуры к ацикличной может
увеличиться размер максимального фрагмента знаний, поэтому применимость подобного преобразования ограничена. Во-вторых, алгоритмы построения дерева смежности возвращают произвольное дерево смежности, тогда как особенности алгоритмов
11 глобального логико-вероятностного вывода, опирающихся на этот граф, выдвигают к
нему дополнительные требования, связанные с минимизацией времени работы алгоритма и числа шагов при распространении свидетельства от одного узла к другому.
Перечисленные затруднения решаются за счет рассмотрения более широкого, чем
деревья смежности, класса графов, а именно минимальных графов смежности.
Минимальный граф смежности граф смежности, число ребер в котором минимально среди всех графов смежности над той же первичной структурой. Минимальные
графы смежности, с одной стороны, существуют над любой первичной структурой, а,
с другой стороны, они минимальны и совпадают с деревьями смежности в случае
ацикличной первичной структуры.
Множество минимальных графов смежности совпадает с множеством деревьев смежности тогда и только тогда, когда связная первичная структура ациклична.
Теорема 3.
Максимальный граф смежности Gmax наибольший по числу ребер граф смежности. Сужение G ? U согласованного нагруженного графа G на непустой сепаратор
U это согласованный нагруженный граф, в который входят только те вершины и
ребра исходного графа G, нагрузки которых содержат или равны U. Через ? U будем
обозначать Gmax ? U.
Сильное сужение G U сужение G ? U, не содержащее ребра нагрузки U. Через
U будем обозначать Gmax U.
Жила нагрузки U граф, множество ребер которого состоит из |Conn( U)| ? 1
элементов, которые имеют нагрузку U и которые при добавлении в граф U делают
его связным, а множество ребер является множеством концов ребер, где Conn ( U) число компонент связности графа U. Пучок граф, построенный путем объединения
жил, выбранных по одной для каждого непустого сепаратора.
Теорема 4. (О множестве минимальных графов смежности). Множество минимальных графов смежности совпадает с множеством пучков.
Теорема о множестве минимальных графов смежности является ключевой, поскольку она конструктивно сопоставляет множеству минимальных графов смежности
декартово произведение множеств жил каждого непустого сепаратора.
Нередуцируемым графом смежности называется такой граф смежности, что при
удалении любого ребра он перестает быть магистрально связным.
(О множестве нередуцируемых графов смежности). Множество
нередуцируемых графов смежности совпадает с множеством минимальных графов смежности.
Теорема 5.
(О матроидном представлении множества магистрально связных
графов). Для первичной структуры, представленной набором подалфавитов V =
^ cmp = hV, Ecmp i над ней че{Ai }i?I , и полного согласованного нагруженного графа G
рез Ibbc обозначим множество всех независимых множеств, построенных над
V , где под независимостью множества A ? Ecmp будем понимать то, что со^ = hV, Ecmp \Ai магистрально связен. Тогда пара
гласованный лексический граф G
M = hEcmp , Ibbc i является матроидом.
Теорема 6.
Теорема о матроидном представлении множества магистрально связных графов
обосновывает возможность использования жадного алгоритма для синтеза некоторого
минимального графа смежности.
12 (О мощности множества минимальных графов смежности). Мощность множества минимальных графов смежности равна
Теорема 7.
nU
Y
!
v(Pi )
i=1
!nU ?2
v(Pi )
,
i=1
U разбивается на nU владений P1 , . . . , PnU .
где
nU
X
Теорема 8.
Число ребер в минимальном графе смежности равно
U?Sep
Conn (
U) ? |Sep| .
X
Основная идея алгоритмизации синтеза минимальных графов смежности состоит
в том, чтобы построить для сепараторов компоненты связности сильных сужений. На
основе множества множеств таких компонент можно синтезировать множество минимальных графов смежности и его подмножества (в том числе одноэлементные), строя
для каждого сепаратора множество или подмножество его жил и перебирая все кортежи по одному из каждого множества и объединяя их в графы.
При этом сложность работы алгоритмов синтеза подмножества минимальных графов смежности линейно зависит от числа элементов в таком подмножестве и полиномиально от числа сепараторов, для которых перебираются владения, поэтому
вместо рассмотрения всего множества непустых сепараторов предлагается рассматривать только стереосепараторы сепараторы, для которых число жил больше одной,
особым образом учитывая остальные сепараторы. Введем их классификацию.
Бисепаратор сепаратор, сужение на который состоит из двух вершин. Обязательное ребро ребро, являющееся жилой бисепаратора.
Утверждение 1.
Обязательное ребро входит в каждый минимальный граф смеж-
ности.
Граф обязательных ребер граф на вершинах первичной структуры, состоящий
только из обязательных ребер. Стереосепаратор сепаратор, которому соответствует более одной жилы. Основной алгоритмов синтеза подмножеств минимальных графов смежности является синтез по заданному набору нагрузок Workloads трех других
множеств: Stereoseparators множества стереосепараторов, Stereoholdings множества владений стереосепараторов и NeccessaryEdges обязательных ребер, по которому строится подмножество минимальных графов смежности.
Предложено шесть алгоритмов синтеза такого множества, работа которых сводится
к следующим шагам (которые в некоторых алгоритмах могут быть объединены в один
или выполняться в ином порядке):
1) построить множество непустых сепараторов Separators;
2) для каждого элемента Separators построить вершины, попадающие в сужение на
него; ребра тех, в которых ровно две вершины, добавить в NeccessaryEdges и исключить
из рассмотрения;
3) для каждого элемента Separators построить владения этого сепаратора, если их
больше одного, то добавить сепаратор к Stereoseparators, а владения к Stereoholdings.
Предложены также модификации этого метода, которые состоят в том, чтобы строить сужения минимальных графов смежности на сепараторы не перебором всех вершин и их сепараторов, но перебором вершин и сепа?
Документ
Категория
Без категории
Просмотров
7
Размер файла
937 Кб
Теги
структура, синтез, обучения, байесовских, сетей, смежности, графов, машинное, глобальные, алгебраический
1/--страниц
Пожаловаться на содержимое документа