автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей

На правах рукописи

ФИЛЬЧЕНКОВ Андрей Александрович

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

05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

2 8 НОЯ 2013

005540138

Санкт-Петербург 2013

005540138

Работа выполнена на кафедре информатики математико-механического факультета федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный универсти-тет» и в лаборатории теоретических и междисциплинарных проблем информатики федерального государственного бюджетного учреждения науки Санкт-Петербургского института информатики и автоматизации Российской академии наук.

Научный руководитель: ТУЛУПЬЕВ Александр Львович,

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

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

Официальные оппоненты: ЯЗЕНИН Александр Васильевич,

доктор физико-математических наук, профессор, федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тверской государственный университет»), факультет прикладной математики и кибернетики, декан

ДОДОНОВА Наталья Леонидовна, кандидат физико-математических наук, доцент, федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Самарский государственный аэрокосмический университет им. академика С.П. Королева (национальный исследовательский университет)», кафедра прикладной математики, доцент

Ведущая организация: федеральное государственное бюджетное учреждение науки

Институт системного анализа Российской академии наук

Защита состоится «13» декабря 2013 г. в 14:00 на заседании диссертационного совета Д 212.215.07, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)» (СГАУ), по адресу: 443086, Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке СГАУ.

Автореферат разослан «11» ноября 2013 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Белоконов И.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Д.А. Поспелов и В.Н. Захаров относили к интеллектуальным методам и технологиям управления в том числе мягкие вычисления, распределенный искусственный интеллект и методы и технологии инженерии знаний и рассуждений на знаниях. Вероятностные графические модели (ВГМ) как область искусственного интеллекта (ИИ) можно отнести к выделенным категориям. Для моделей этого класса общим является локализация вычислений, основанная на принципе декомпозиции и предположениях об условной независимости. ВГМ представляют собой граф, узлам которого приписаны случайные элементы, а ребра определенным образом отображают зависимости между ними.

Алгебраические байесовские сети (ABC), предложенные В.И. Городецким, представляют собой логико-вероятностную графическую модель, опирающуюся на логико-вероятностный подход в интерпретации, выдвинутой Н. Нильссоном для теоретических основ и приложений ИИ. Ключевым отличием ABC от других моделей является представление неопределенности через интервальные оценки вероятности истинности пропозициональных формул. Проблема представления неопределенности знаний освещалась в работах В.Н. Вагина, Ю.Р. Валькмана, A.C. Нариньяни, Г.С. Осипова, Д.А. Поспелова, В.В. Тарасова, Н.Г. Ярушкиной, A. Dempster, D. Dubois, J. Pearl, R. Pagin, J. Halpern, K. Korb, H. Prade, G. Shafer, L. Zadeh и многих других.

Теория ВГМ нуждается в моделях, методах и алгоритмах машинного (автоматического) обучения1, в частности, автоматического синтеза глобальных структур таких моделей и автоматического построения оценок их параметров по исходным данным. Комплексная проблема глобального обучения ABC заключается в алгоритмизации синтеза глобальных структур ABC. Среди них выделяют первичную структуру, представляющую собой набор максимальных по включению фрагментов знаний (ФЗ), и вторичную структуру, в данной работе рассматриваемую как граф, построенный над элементами первичной структуры и обладающий особым свойством магистральной связности.

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

Обоснование актуальности исследований также содержит формальную сторону: тема настоящего диссертационного исследования ассоциирована с пунктом 35 «Когнитивные системы и технологии, ..., искусственный интеллект.....принятие решений

при многих критериях» Программы фундаментальных научных исследований государственных академий наук на 2013-2020 годы (утверждена Распоряжением Правительства РФ от 03.12.2012 г. № 2237-р) в части «теоретические и технологические основы, алгоритмическое обеспечение и программный инструментарий вероятностных графических моделей, логико-вероятностных графических моделей, ... ».

1 Машинное обучение — одна из областей ИИ, связанная с разработкой моделей и алгоритмов, позволяющих вычислительной машине делать предсказания, основываясь на примерах или предыдущем опыте (Alpaydin Е. Introduction to Machine Learning. 2nd Ed. Cambridge, MS: The MIT Press, 2010. 537 p.)

Степень разработанности темы. В работах A.A. Тулупьева в качестве вторичной структуры ABC рассматриваются деревья смежности, для которых были предложены алгоритмы глобального логико-вероятностного вывода и эффективного поддержания глобальной непротиворечивости. Также в них был предложен подход к устранению отдельных простых циклов графа смежности, и, совместно с соавторами (в первую очередь, с соискателем A.A. Фильченковым) — подход к синтезу множества минимальных графов смежности. A.B. Сироткин формализовал понятие магистральной связности как специфического свойства графов смежности. В.В. Опарин выдвинул идею одного из вариантов синтеза минимального графа смежности, сводящуюся к использованию жадного алгоритма.

Исследованиями по выявлению и устранению цикличности гиперграфов занимались В.В. Быкова, С. Beeri, G. Dirac, R. Pagin, M. Goodman, D. Maier, A. Mendelzon, N. Robertson, D. Rose, P. Seymour, R. Tarjan, J. Ullman, M. Yannakakis и многие другие. Так, известны алгоритмы выявления цикличности гиперграфа и классы алгоритмов ее устранения, которые мотивировали часть подходов к решению задач диссертационного исследования.

Объект исследования — система глобальных структур ABC как специальных графов и гиперграфов. Предмет исследования — вторичная структура ABC, формализуемая как граф смежности, и машинное обучение этой структуры посредством синтеза графов смежности.

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

1) выявить критерии существования связной вторичной структуры и, отдельно, ацикличной вторичной структуры над заданной первичной структурой АБС по косвенным признакам (т.е. не предполагающим непосредственное построение вторичной структуры);

2) разработать методы преобразования первичной структуры АБС к структуре, над которой существует ацикличная вторичная структура, и указать факторы, ограничивающие применимость таких методов;

3) выявить свойства минимальных по числу ребер графов смежности, которые могут выступать в качестве вторичной структуры ABC и существующие над произвольной первичной структурой, описать структуру такого множества и вывести формулы для расчета мощности множества минимальных графов смежности и числа ребер такого графа;

4) разработать систему алгоритмов синтеза множества минимальных графов смежности, а также подмножеств этого множества, адаптированных к таким особенностям алгоритмов логико-вероятностного вывода в теории АБС, как число шагов в пропага-ции свидетельства между узлами графа и распараллеливаемость этой пропагации;

5) реализовать описанные алгоритмы синтеза вторичной структуры АБС, а также анализа и преобразования первичной структуры в прототипе комплекса программ для вычислительных экспериментов.

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

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

Научная новизна. Все результаты, выдвигаемые на защиту, являются новыми.

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

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

Разработаны программные компоненты, дополняющие существующий комплекс программ для работы с ABC и реализующие алгоритмы синтеза вторичной структуры ABC, алгоритмы выявления существования дерева смежности над заданной первичной структурой ABC и ее преобразования к структуре допускающей, над которой существует дерево смежности.

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

Результаты диссертационного исследования докладывались и обсуждались на следующих научных мероприятиях: 1) Научная сессия НИЯУ МИФИ-2011 (1-5 февраля 2011 г., Москва); 2) VI Междунар. науч.-практ. конф-я «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (16-19 мая 2011 г., Коломна); 3) VII С.-Петерб. межрегион, конф-я «Информационная безопасность регионов России (ИВРР-2011)» (26-28 октября 2011 г., С.-Петерб); 4) VI Междунар. науч.-практ. конф-я «Современные информационные технологии и IT-образование» (12-14 декабря 2011 г., Москва); 5) Научная сессия НИЯУ МИФИ-2012 (30 января-4 февраля 2012 г., Москва); 6) Всеросс. науч. конф-я по проблемам информатики СПИСОК-2012 (2527 апреля 2012 г., С.-Петерб.); 7) VI Междунар. науч.-технич. конф-я молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем» (21-24 мая 2012 г., Пенза); 8) XV Междунар. конф-я по мягким вычислениям и измерениям (SCM'2012) (25-27 июня 2012 г., С.-Петерб.); 9) 1-й Междунар. симпозиум «Гибридные и синергетические интеллекту-

альные системы: теория и практика» (29 июня - 2 июля 2012 г., Калининград); 10) The 6th Russian Summer School in Information Retrieval (RuSSIR 2012) (August 6-10, 2012. Yaroslavl, Russia); 11) 35-я конф-я молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (19-25 августа 2012 г., Петрозаводск); 12) 5-я росс, мультиконф-я по проблемам управления/конф-я «Информационные технологии в управлении-2012» (ИТУ-2012) (9-11 октября 2012 г., С.-Петерб.); 13) Юбилейная XIII С.-Петерб. междунар. конф-я «Региональная информатика (РИ-2012)» (24-26 октября 2012 г., С.-Петерб.); 14) Междунар. (44-я Всеросс.) молодежная школа-конф-я «Современные проблемы информатики-2013) (27 января - 2 февраля 2013 г., Екатеринбург); 15) Научная сессия НИЯУ МИФИ-2013 (1-6 февраля 2013 г., Москва); 16) Всеросс. науч. конф-я по проблемам информатики СПИСОК-2013 (23-26 апреля 2013 г., С.-Петерб.). Кроме того, результаты диссертационного исследования докладывались на Санкт-Петербургском городском научном семинаре «Информатика и компьютерные технологии» в 2013 году и на заседании Ученого совета СПИИРАН в 2013 году.

Исследования по тематике диссертации были поддержаны: 1) грантом РФФИ, проект № 09-01-00861-а «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью», 2) грантом РФФИ, проект 12-01-00945-а «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», 3) грантом Правительства Санкт-Петербурга для победителей конкурса грантов Санкт-Петербурга для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2010 г., № 2.1/03-06/018, 4) грантом РФФИ, проект 12-01-31202 мол_а «Развитие теории графов смежности для автоматического обучения баз знаний с неопределенностью на основе алгебраических байесовских сетей», 5) грантом РФФИ, проект 12-01-16030-моб_з_рос «Косвенные признаки цикличности вторичной структуры алгебраической байесовской сети» для представления на научном мероприятии «1-й Международный симпозиум "Гибридные и синергетические интеллектуальные системы: теория и практика (ГиСИС'12)"». Соискатель является руководителем проектов №№ 3-5.

Теоретическая и практическая значимость исследования. Результаты диссертационного исследования развивают теоретическую и технологическую базу для решения задач в системах поддержки принятия решений, в частности для представления и обработки неточной, неполной, нечисловой информации о соотношении вероятностей истинности утверждений, на основе которых принимаются решения, и для комбинирования или агрегирования такой информации из источников, степени доверия к которым могут различаться или быть неизвестными. Кроме того, полученные результаты в отношении минимальных по числу ребер графов смежности имеют теоретическую значимость для раздела теории графов, связанного с графами смежности. Результаты исследований вошли в научные отчеты СПИИРАНа по следующим НИР: «Логико-вероятностный подход и его обобщения в моделировании, обработке и обучении баз фрагментов знаний с неопределенностью в интеллектуальных системах», шифр BNet-2008, номер государственной регистрации 01200852455, «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью», номер государственной регистрации 01200963057, «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», номер государственной регистрации 01201259408.

-б-

Полученные результаты могут использоваться в учебном процессе для студентов, специализирующихся в области информатики и родственных ей дисциплин. В частности, результаты были включены в программы спецкурса «Теория байесовских сетей» и (частично) спецкурса «СУВД, интерфейс и интеллектуальные модели в комплексах программ» математико-механического факультета СПбГУ.

Публикации. По теме диссертации было сделано 58 публикаций и приравненных к ним научных работ, из них 22 статьи (из которых 6 единоличных) в изданиях из «Перечня рецензируемых научных журналов и изданий для опубликования основных научных результатов», утвержденного ВАК, 25 статей и докладов на научных конференциях (из которых 9 единоличных), 11 зарегистрированных программ ЭВМ и алгоритмов (3 — в РОСПАТЕНТе и 8 — в ОФЭРНиО/ЦИТиСе). В дополнение к перечисленному материалы диссертационного исследования нашли отражение в 15 тезисах научных конференций и 5 прошедших госрегистрацию в ЦИТиС научных отчетах.

Личный вклад A.A. Фильченкова в ключевых публикациях с соавторами кратко характеризуется следующим образом: В [1] ему принадлежит доказательство теоремы о матроидном представлении, а также теорема о совпадении множеств минимальных и нередуцируемых графов смежности и доказательство ее корректность на основе теоремы о матроидном представлении; в [2] — формулировки и доказательства утверждений и лемм о свойствах торакса; в [3] — теорема о циклах в минимальных графах смежности и ее доказательство; в [5] — основные утверждения и леммы, их доказательство и доказательство теоремы о множестве минимальных графов смежности; в [10] — доказательство теоремы о совпадении множеств минимальных и нередуцируемых графов смежности, не основывающееся на корректности теоремы о матроидном представлении; в [19] — формулировка утверждений о связности первичной структуры и их доказательства; в [8] — описание задач глобального обучения АБС и подходов к их решению; в [9,12] — алгоритмы выявления цикличности первичной структуры и доказательства их корректности; в [6] — формализация третичной структуры и описание ее свойств; в [11] — методы устранения циклов и доказательство их корректности; в [14] — моделирование процесса распространения свидетельств по графу смежности распространением свидетельств по родительскому графу над множеством непустых сепараторов; в [16] — новое, уточненное доказательство теоремы о циклах в минимальных графах смежности; в [18] — формулировки основных утверждений и идеи их доказательства, а также описание алгоритма и доказательство его корректности; в [21] — алгоритмы, а также доказательство их корректности; в [20] — представление первичной стурктуры ABC как гиперграфа и сведение задачи преобразования такой структуры к ациклической к задачам, решаемым методами графовой декомпозиции.

Более подробно личный вклад A.A. Фильченкова в совместных публикациях и приравненных к ним работах описан в тексте диссертации.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списков используемой литературы и иллюстраций. Нумерация разделов, рисунков, формул, структурных элементов текста ведется отдельно для каждой главы. Общий объем работы составляет 339 страниц. Список используемой литературы содержит 371 источник.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

В автореферате изложены только основные определения, теоремы, утверждения и формулы. Нумерация теорем и утверждений самостоятельная и не зависит от нумерации указанных элементов в тексте диссертации.

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

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

Вторая глава содержит необходимые для дальнейшего изложения материалы, в ней приводятся основы вероятностной логики в формализации Дж. Хальперна, Р. Фэй-джина и Н. Меджиддо, теории конечных графов (в том числе гиперграфов), теории упорядоченных множеств и теории АБС, основанной на результатах работ В.И. Городецкого, A.A. Тулупьева и A.B. Сироткина.

Алфавит — конечное множество атомарных пропозициональных формул (переменных) А = {xi,..., Хп}, которые для краткости будем называть атомами. Конъюнктом над А называется конъюнкция некоторого поднабора (возможно, полного) положительно означенных атомов этого алфавита (но не их отрицаний): Xí,Xí2 ...xim) где {ii,... ,im] С {1,... ,п}. Идеалом конъюнктов над А называется множество всех непустых конъюнктов, построенных над А. Идеал конъюнктов обозначается как С = С(А), его мощность равна 2П — 1.

Фрагмент знаний со скалярными оценками — это пара вида (С(А),р), где р — функция: р : 6(A) —> [0;1]. Фрагмент знаний с интервальными оценками — это пара вида (С(А),р), где р — функция: р : е(А) —► {[a;b] | 0 < а < Ъ < 1}.

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

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

Через I обозначим некоторое конечное упорядоченное подмножество индексов элементов алфавита A, {AíKsi — покрывающее семейство подалфавитов алфавита А, {(e(Ai),pA.)} — семейство фрагментов знаний с интервальными оценками рА., построенными над подалфавитами из {Atligi. Фрагменты знаний в наборе называются максимальными, если ни один элемент из {C(Ai)}iei не содержит никакой другой.

Первичная структура ABC PSi = {(£(А0,рА.)}igI — это набор максимальных фрагментов знаний (МФЗ). Вероятностной семантикой Sem(PSi) первичной структуры PSi = {(Ca¿ , Ра i )}ieI с интервальными оценками называется семейство таких вероятностных распределений рА) рА : С(А) —> [0;1], значения которых для каждого фрагмента знаний на его элементах попадают в соответствующие интервалы оценки истинности: Sem(PSi) = {Pa|Vc G Uisi е(А0 Pa € PAt (с)}.

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

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

В третьей главе вводится система терминов для описания глобальных структур АБС, сформулированы и доказаны теоретические результаты диссертационного исследования. Используется система терминов, составленная на основе [1,5,6,11,14-16,18, 19,23,24], ее основные элементы изложены ниже..

Нагруженный граф — тройка (G, A,W), где G — граф, А — алфавит атомов, W — функция нагрузки, заданная на множествах вершин и ребер G со значениями из 2А (т.е. всевозможными подмножествами А). Нагрузкой подграфа нагруженного графа называется пересечение нагрузок его вершин: W(G) = Dvcevígi W(v). Сепаратором двух вершин в нагруженном графе является пересечение их нагрузок: Sep(u,v) = W(u) П W(v). Множество всех непустых сепараторов обозначим Sep. Две вершины называются сочлененными, если их сепаратор непуст.

Согласованный нагруженный граф — такой нагруженный граф, что нагрузка любого ребра равна сепаратору концов этого ребра: V(u,v) £ Е W((u,v)) = Sep(u,v). Граф МФЗ — согласованный нагруженный граф, вершины которого соответствуют по-далфавитам, над которыми построены идеалы соответствующих максимальных фрагментов знаний, а ребра в котором могут быть проведены только между сочлененными вершинами. Магистральный путь (vi,..., vn) между двумя сочлененными вершинами vi и vn, п > 2 — это путь, в котором нагрузка каждой вершины содержит сепаратор его концов: Vi € {2,... ,п — 1} Sep(vi,vn) С W(ví). Магистралъно связный граф — это согласованный нагруженный граф, в котором каждая пара сочлененных вершин соединена магистральным путем.

Граф смежности — магистралъно связный граф МФЗ. Итак, граф смежности был формализован как особый объект, который определен через тройку {G,A, W). Таким

Рис. 1. Вторичная структура АБС над ее первичной структурой (сверху), соответствующая графу смежности (снизу).

образом, формализуется первичная структура АБС: алфавит, над которым она построена, соответствует А, а подалфавиты, над которыми построены фрагменты знаний, являются значениями W для соответствующих вершин. На рис. 1 приведен пример вторичной структуры, и пример графа смежности, которому соответствует эта вторичная структура.

Рассмотрим вопросы выявления и устранения цикличности в первичной структуре, которая представляется набором подалфавитов: PSi = {Ai}igi, где I — некоторое конечное множество индексов, заданных над подалфавитами алфавита А. Формализовать первичную структуру можно как гиперграф (A,{Ai}igi), ребрами которого выступают подалфавиты фрагментов знаний (рис. 2).

Связная первичная структура — это первичная структура, над которой существует связный граф смежности. Ацикличная первичная структура — это первичная структура, над которой существует ацикличный граф смежности.

Протоструктура ABC с первичной структурой {Ai}iei — это граф, построенный над алфавитом А, ребра которого соединяют два атома в том и только том случае, если они входят в какой-либо подалфавит Ai (рис. 2). Протоструктура является первичным графом гиперграфа, соответствующего первичной структуре ABC. Задачи выявления связности и ацикличности первичной структуры сведены к задачам выявления связности и ацикличности гиперграфа, решаемым методами графовой декомпозиции: первичная структура ациклична тогда и только тогда, когда ее протоструктура три-ангулярна, а ее ребра совпадают с вершинами максимальных клик протоструктуры. Помимо этого предложны также иные способы выявления ацикличности первичной структуры по косвенным признакам, основанные на оценке числа ребер в минимальном графе смежности и выявлении особых циклов в четвертичной структуре ABC — (полусиблингових небратских простых циклов).

Рассмотрим вопрос о возможности преобразования первичной структуры к ацикличной. При таком преобразовании должна сохраняться ее вероятностная семантика.

Теорема 1. (О единственности согласованной первичной структуры). Для заданной над семейством подалфавитов {Ai}igi согласованной первичной структуры PSIi не существует отличной согласованной первичной структуры над тем же набором подалфавитов, стохастически эквивалентной исходной.

Для двух: минимальных гиперграфов H = (А, Е) и H' = (А, Е') будем говорить, что H меньше Н', если для любого ребра из H можно указать ребро из Е', которое совпадает с ним или содержит его: H < H' -гф Ve 6 Е Зе' € Е' : е С е'.

Теорема 2. (О построении семантически эквивалентных первичных структур с интервальными оценками). Пусть задана согласованная первичная структура PSIi с интервальными оценками над семейством подалфавитов {At}igi. Тогда для любого множества индексов J, такого, что (A,{Ai}igi) < (A,{Aj}jgj), можно построить согласованную первичную структуру PSIj Kaá{Aj}jgj, стохастически эквивалентную исходной, причем единственным способом.

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

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

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

Перечисленные затруднения решаются за счет рассмотрения более широкого, чем деревья смежности, класса графов, а именно — минимальных графов смежности.

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

Теорема 3. Множество минимальных графов смежности совпадает с множеством деревьев смежности тогда и только тогда, когда связная первичная структура ациклична.

Максимальный граф смежности Стах — наибольший по числу ребер граф смежности. Сужение й 1II согласованного нагруженного графа С на непустой сепаратор И — это согласованный нагруженный граф, в который входят только те'вершины и ребра исходного графа й, нагрузки которых содержат или равны II. Через X и будем обозначать Стах 1 и.

Сильное сужение С ! II — сужение С X и, не содержащее ребра нагрузки II. Через | II будем обозначать йшах 1Ч.

Жила нагрузки II — граф, множество ребер которого состоит из |Сопп(|11)| — 1 элементов, которые имеют нагрузку II и которые при добавлении в граф I И делают его связным, а множество ребер является множеством концов ребер, где Сопп(|11) — число компонент связности графа i И. Пучок — граф, построенный путем объединения жил, выбранных по одной для каждого непустого сепаратора.

Теорема 4. (О множестве минимальных графов смежности). Множество минимальных графов смежности совпадает с множеством пучков.

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

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

Теорема 5. (О множестве нередуцируемых графов смежности). Множество нередуцируемых графов смежности совпадает с множеством минимальных графов смежности.

Теорема 6. (О матроидном представлении множества магистрально связных графов). Для первичной структуры, представленной набором подалфавитов V = {А^Кеь и полного согласованного нагруженного графа 6СтР = (V, Естр) над ней через 1ььс обозначим множество всех независимых множеств, построенных над V, где под независимостью множества А С ЕСтр будем понимать то, что согласованный лексический граф б = (V, ЕСтР\А) магистрально связен. Тогда пара М = (Естр, 1ььс) является матроидом.

Теорема о матроидном представлении множества магистрально связных графов обосновывает возможность использования жадного алгоритма для синтеза некоторого минимального графа смежности.

Теорема 7. (О мощности множества минимальных графов смежности). Мощность множества минимальных графов смежности равна

/пи \ /пи \пи—2

i nv(pt)J (Z.v(Pi)J

где | U разбивается на "Пи владений Pi,..., Рпи *

Теорема 8. Число ребер в минимальном графе смежности равно

Y_ Conn U) — |Sep|.

USSep

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

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

Висепаратор — сепаратор, сужение на который состоит из двух вершин. Обязательное ребро — ребро, являющееся жилой бисепаратора.

"Утверждение 1. Обязательное ребро входит в каждый минимальный граф смежности.

Граф обязательных ребер — граф на вершинах первичной структуры, состоящий только из обязательных ребер. Стереосепаратор — сепаратор, которому соответствует более одной жилы. Основной алгоритмов синтеза подмножеств минимальных графов смежности является синтез по заданному набору нагрузок Workloads трех других множеств: Stereoseparators — множества стереосепараторов, Stereoholdings — множества владений стереосепараторов и NeccessaryEdges — обязательных ребер, по которому строится подмножество минимальных графов смежности.

Предложено шесть алгоритмов синтеза такого множества, работа которых сводится к следующим шагам (которые в некоторых алгоритмах могут быть объединены в один или выполняться в ином порядке):

1) построить множество непустых сепараторов Separators;

2) для каждого элемента Separators построить вершины, попадающие в сужение на него; ребра тех, в которых ровно две вершины, добавить в NeccessaryEdges и исключить из рассмотрения;

3) для каждого элемента Separators построить владения этого сепаратора, если их больше одного, то добавить сепаратор к Stereoseparators, а владения — к Stereoholdings.

Предложены также модификации этого метода, которые состоят в том, чтобы строить сужения минимальных графов смежности на сепараторы не перебором всех вершин и их сепараторов, но перебором вершин и сепараторов, попавших в сужение на сепаратора-родителя. Это, однако, предполагает построение родительского графа —

т.е. третичной структуры. Другая модификация состоит в том, чтобы выявлять владения на основе полусиблингового графа для соответствующего сепаратора. Собственная вершина сепаратора U — такая вершина V, что для некоторой другой вершины и Sep(v, и) = U. Еще одно улучшение связано с построением только множества собственных вершин вместо построения сужения.

Оценка сложности таких алгоритмов лежит в классе 0(mw2 + msw + sw2 + ms2), где w — число фрагментов знаний в первичной структуре, m — максимальное число атомов во фрагменте знаний, as — число непустых сепараторов.

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

Рандомизированный алгоритм синтеза минимальных графов смежности строит минимальный граф смежности с ненулевой вероятностью.

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

1) выявление связности первичной структуры;

2) построение множества непустых сепараторов Separators;

3) построение владений для каждого сепаратора;

4) проверка того, что число владений всех непустых сепараторов, уменьшенному на число непустых сепараторов, равно числу фрагментов знаний, уменьшенному на 1.

Алгоритм выявления ацикличности первичной структуры на основе выявления по-лусиблинговых небратских простых циклов состоит из следующих шагов:

1) построение множества Separators;

2) построение родительского графа над замкнутым сверху множеством непустых сепараторов;

3) построение для каждого сепаратора полусиблингового графа;

4) поиск в каждом полусиблинговом графе полусиблинговых небратских простых циклов.

В четвертой главе описываются основные моменты программной реализации прототипа комплекса программ для вычислительных экспериментов. Описана структура комплекса программ, разделенного на четыре основных пакета, один из которых содержит классы и методы для выявления и устранения цикличности первичной структуры, другой — для синтеза множества минимальных графов смежности и его подмножеств, третий — для сохранения и загрузки полученных результатов и четвертый содержит панель графического пользовательского интерфейса.

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

Заключение содержит основные результаты и выводы по диссертационной работе.

ЗАКЛЮЧЕНИЕ

Основные результаты диссертационного исследования:

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

2) предложены и обоснованы методы устранения цикличности графа смежности за счет пополнения первичной структуры фрагментами знаний, устраняющих полусиб-линговые небратские простые циклы; предложены и обоснованы методы преобразования первичной структуры ABC к ацикличной структуре с той же вероятностной семантикой через сведение соответствующего ей гиперграфа к ацикличному (за счет сведения исходной задачи к задачам, решаемыми методами графовой декомпозиции, на основе введенной формализации первичной структуры);

3) сформулирован комплекс теорем, сопоставляющих множеству минимальных графов смежности декартово произведение множеств жил каждого непустого сепаратора, выражающих мощность этого множества, его эквивалентность множеству нередуци-руемых графов смежности, число ребер в минимальном графе смежности, указанные теоремы доказаны; составлена систематизация глобальных структур АБС на основе графового и гиперграфового представления;

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, опубликованные в изданиях из «Перечня рецензируемых научных журналов и изданий для опубликования основных научных результатов »

1. Опарин В.В., Филъненков A.A., Тулупъев А.Л., Сироткин A.B. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. Вып. 4. С. 73-76.

2. Филъченков A.A., Тулупъев А.Л. Понятие торакса в применении к исследованию графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 1 (16). С. 186-205.

3. Филъченков A.A., Тулупъев A.A. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Труды СПИИРАН. 2011. Вып. 2 (17). С. 151-173.

4. Филъченков A.A. Алгоритмы построения третичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 2(17). С. 197-218.

5. Филъченков A.A., Тулупъев A.A., Сироткин А.В. Структурный анализ клик максимальных графов смежности алгебраических байесовских сетей // Вестн. Тверск. гос. ун-та. Сер.: Прикладная математика. 2011. №20. С. 139-151.

6. Филъченков A.A., Тулупъев A.A. Третичная структура алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 3 (18). С. 164-187.

7. Филъченков A.A. Алгоритмы построения элементов третичной полиструктуры алгебраической байесовской сети // Труды СПИИРАН. 2011. Вып. 3 (18). С. 237-266.

8. Тулупъев A.A., Филъченков A.A., Валътпман H.A. Алгебраические байесовские сети: задачи автоматического обучения // Информационно-измерительные и управляющие системы. 2011. № 11, т. 9. С. 57-61.

9. Филъченков A.A., Тулупъев A.A. Алгоритм выявления ацикличности первичной структуры алгебраической байесовской сети по ее четвертичной структуре // Труды СПИИРАН. 2011. Вып. 4(19). С. 128-145.

10. Филъченков A.A., Тулупъев A.A. Совпадение множеств минимальных и нередуцируемых графов смежности над первичной структурой алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2012. Вып. 2. С. 69—78.

11. Филъченков A.A., Фроленков К.В., Тулупъев А.А. Устранение циклов во вторичной структуре алгебраической байесовской сети на основе анализа ее четвертичной структуры // Труды СПИИРАН. 2012. Вып. 2(21). С. 143-156.

12. Филъченков A.A. Тулупъев А.Л. Алгоритм выявления ацикличности первичной структуры алгебраической байесовской сети на основе оценки числа ребер в минимальном графе смежности // Труды СПИИРАН. 2012. Вып. 3(22). С. 205-223.

13. Филъченков A.A. Меры истинности и вероятностные графические модели для представления знаний с неопределенностью // Труды СПИИРАН. 2012. Вып. 4(23). С. 254—295.

14. Фроленков К.В., Филъченков A.A., Тулупъев A.A. Апостериорный вывод в третичной полиструктуре алгебраических байесовских сетей // Труды СПИИРАН. 2012. Вып.. 4(23). С. 343-356.

15. Филъченков A.A. Иерархия глобальных структур алгебраической байесовской сети как система графов и гиперграфов // Научно-технический вестник информационных технологий, механики и оптики. 2013. Вып. 1(83). С. 75-80.

16. Фроленков К.В., Филъченков A.A., Тулупъев A.A. Сиблинговый критерий цикличности минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 2(25). С. 190-203.

17. Филъченков A.A. Субоптимальная звездчатая структура алгебраической байесовской сети // Информационно-управляющие системы. 2013. Вып. 2. С. 13—17.

18. Филъченков A.A., Мусина В.Ф., Тулупъев A.A. Алгоритм рандомизированного синтеза минимального графа смежности // Труды СПИИРАН. 2013. Вып. 2(35). С. 221—234.

19. Филъченков A.A., Тулупъев A.A. Связность и ацикличность первичной структуры алгебраической байесовской сети // Вестник Санкт-Петербургского государственного университета. Серия 1. Математика. Механика. Астрономия. 2013. Вып. 1. С. 110—119.

20. Вяткин A.B., Филъченков A.A., Тулупъев A.A., Мусина В.Ф., Фроленков К.В. Подходы к устранению цикличности первичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2013. Вып. 3(26). С. 216-233.

21. Филъченков A.A., Фроленков К.В., Сироткин A.B., Тулупъев A.A. Система алгоритмов синтеза подмножеств минимальных графов смежности // Труды СПИИРАН. 2013. Вып. 4(27). С. 200—244.

22. Филъченков A.A. Преобразование первичной структуры алгебраической байесовской сети к ациклической с сохранением вероятностной семантики // Труды СПИИРАН. Вып. 7(30). С. 141—153.

Научные статьи и доклады, опубликованные в других изданиях

23. Филъненков A.A., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. Вып. 11. СПб. Наука, 2009. С. 104-127.

24. Филъненков A.A., Тулупьев A.A., Сироткин A.B. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. Вып. 1 (12). С. 97-118.

25. Филъненков A.A. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик // Труды СПИИРАН. 2010. Вып. 1(12). С. 119-133.

26. Фххлъненков A.A., Тулупьев A.A., Сироткин A.B. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 2(13). С. 87105.

27. Филъненков A.A. Алгоритм построения множества минимальных графов смежности при помощи клик владений // Труды СПИИРАН. 2010. Вып. 2(13). С. 67-86.

28. Филъненков A.A., Тулупьев A.A., Сироткин A.B. Ребра графов смежности в контексте компаративного анализа клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. 2010. Вып. 3(14). С. 132-149.

29. Филъненков A.A. Алгоритм построения множества минимальных графов смежности при помощи самоуправляемых клик-собственников // Труды СПИИРАН. 2010. Вып. 3(14). С. 150-169.

30. Филъненков A.A., Тулупьев А.Л., Сироткин A.B. Мощность множества минимальных графов смежности // Труды СПИИРАН. 2010. Вып. 4(15). С. 136-161.

31. Филъненков A.A. Алгоритм построения множества минимальных графов смежности при помощи клик-собственников владений // Труды СПИИРАН. 2010. Вып. 4(15). С. 193-212.

32. Филъненков A.A., Тулупьев А.Л., Сироткин A.B. Минимальные графы смежности алгебраической байесовской сети: формализация основ синтеза и автоматического обучения // Нечеткие системы и мягкие вычисления. Научный журнал Российской ассоциации нечетких систем и-мягких вычислений. 2011. Том 6, X« 2. С. 145-163.

33. 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. 106-113.

34. Тулупьев A.A., Филъненков A.A., Валътман H.A., Мусина В.Ф. Состояние и перспективы развития подходов к автоматическому обучению алгебраических байесовских сетей // VI-я Международная научно-практическая конф-я «Интегрированные модели и мягкие вычисления в искусственном интеллекте». (16-19 мая 2011 г., Коломна.) Сборник научных трудов. Т. 1. М.: Физмат, 2011. С. 1001-1012.

35. Филъненков A.A. Анализ вторичной структуры алгебраической байесовской сети // VI-я Международная научно-практическая конф-я «Интегрированные модели и мягкие вычисления в искусственном интеллекте». (16-19 мая 2011 г., Коломна.) Сборник научных трудов. Т. 1. М.: Физмат, 2011. С. 1013-1024.

36. Тулупьев А.Л., Филъненков A.A. Иерархия глобальных структур в задачах автоматического обучения алгебраических байесовских сетей //VI Международная научно-практическая конф-я «Современные информационные технологии и IT-образование». (12-14 декабря 2011 г., Москва.) Сборник научных трудов. М. 2011. С. 490-496.

37. Филъненков A.A. Алгоритм выявления цикличности первичной структуры алгебраической байесовской сети //VI Международная научно-практическая конф-я «Современные информационные технологии и IT-образование». (12-14 декабря 2011 г., Москва.) Сборник научных трудов. М. 2011. С. 496-504.

38. Филъненков A.A., Тулупьев А.Л. Вычисление мощности множества минимальных графов смежности // СПИСОК-2012: Материалы всероссийской научной конф-и по проблемам информатики (25-27 апреля 2012 г., Санкт-Петербург). СПб.: ВВМ, 2012. С. 378-384.

39. Филъненков A.A. Междисциплинарные связи в преподавании теории алгебраических байесовских сетей //VI Международная научно-практическая конф-я молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем». (21-24 мая 2012 г., Пенза.) Сборник статей. Пенза: Приволжский дом знаний. 2012 г. С. 182-185.

40. Филъненков A.A. Визуальная инструментальная платформа для работы с алгебраическими байесовскими сетями // XV Международная конф-я по мягким вычислениям и измерениям SCM'12, (25-27 июня 2012 г., Санкт-Петербург.) Сборник докладов. Т. 1. СПб: ЛЭТИ. 2012. С. 195-199.

41. Филъненков A.A., Фроленков К.В., Тулупьев A.A. Программная реализация выявления цикличности алгебраической байесовской сети по косвенным признакам // XV Международная конф-я по мягким вычислениям и измерениям SCM'12. (25-27 июня 2012 г., Санкт-Петербург.) Сборник докладов. Т. 1. СПб: ЛЭТИ. 2012. С. 200-204.

42. Филъненков A.A., Фроленков К.В., Тулупьев А.Л. Представление и визуализация вторичной структуры алгебраических байесовских сетей в комплексе программ // XV Международная конф-я по мягким вычислениям и измерениям SCM'12. (25-27 июня 2012 г., Санкт-Петербург.) Сборник докладов. Т. 1. СПб: ЛЭТИ. 2012. С. 210-214.

43. Филъненков A.A., Тулупьев A.A. Косвенные признаки цикличности вторичной структуры алгебраической байесовской сети // «Гибридные и синергетические интеллектуальные системы: теория и практика» (29 июня - 2 июля 2012 г., Калининград). Материалы 1-го международного симпозиума. Т. 2. Калининград: БФУ им. Канта.2012. С. 9-18.

44. Фроленков К.В., Филъненков A.A. Методы устранения циклов вторичной структуры алгебраической байесовской сети // «Гибридные и синергетические интеллектуальные системы: теория и

практика» (29 июня - 2 июля 2012 г., Калининград). Материалы 1-го международного симпозиума. Т. 2. Калининград: БФУ им. Канта.2012. С. 282-292.

45. Филъненков А.А. Алгебраическая байесовская сеть как основа для медицинской диагностической модели // «Математическое и компьютерное моделирование в биологии и химии. Перспективы развития». (28-30 мая 2012 г., Казань). Сборник трудов I Международной интернет-конф-и. Казань.: Из-во «Казанский университет». 2012.С. 162-166.

46. Филъченков А.А., Сироткин А.В. Выявление ацикличности вторичной структуры алгебраической байесовской сети на основе подсчета числа ее ребер // 35-я конф-я молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы - 2012». (19-25 августа 2012 г., Петрозаводск). Сборник трудов. С. 24-28.

47. Филъненков А.А., Тулупъев А.Л., Сироткин А.В. Управление глобальной структурой знаний в интеллектуальных системах, основанных на алгебраических байесовских сетях // Материалы конф-и «Информационные технологии в управлении» (ИТУ-2012) (9-11 октября 2012 г., Санкт-Петербург). СПб.: ОАО «Концерн «ЦНИИ «Электроприбор». 2012. С. 25-33.

Зарегистрированные программы для ЭВМ и алгоритмы

48. Тулупъеэ А.Л., Филъченков А.А., Сироткин А.В. Программа для поддержки синтеза наборов бинарных последовательностей без поглощающих элементов при формировании алгебраической байесовской сети Algebraic Bayesian Networks Primary Structure Refîner, Version 01 for Java (AlgBNPSRj.v.01) // Свид. о гос. рег. прогр. для ЭВМ. Рег. № 2010614270(30.06.2010). РОСПАТЕНТ // Бюлл. «Прогр. для ЭВМ, БД, топол. инт. микросх.». 2010. №3. С. 456.

49. Тулупъев А.Л., Филъченков А.А., Сироткин А.В. Программа для визуализации операций по формированию первичной структуры алгебраической байесовской сети Algebraic Bayesian Networks Primary Structure Visualizer, Version 01 forJava (AlgBNPSVj.v.01) // Свид. о гос. рег. прогр. для ЭВМ. Рег. X» 2010614268(30.06.2010). РОСПАТЕНТ // Бюлл. «Прогр. для ЭВМ, БД, топол. инт. микросх.». 2010. №3. С. 455.

50. Тулупъев А.Л., Филъченков А.А., Сироткин А.В. Программа для синтеза семейства минимальных графов смежности Algebraic Bayesian Networks Secondary Structures Generator, Version 01 for Java (AIgBNSSGj.v.01) // Свид. о гос. рег. прогр. для ЭВМ. Рег. № 2010614269(30.06.2010). РОСПАТЕНТ // Бюлл. «Прогр. для ЭВМ, БД, топол. инт. микросх.». 2010. №3. С. 455-456.

51. Тулупъев А.Л., Филъченков А.А., Сироткин А.В. Система для построения и визуализации семейства минимальных вторичных структур алгебраической байесовской сети, соответствующих ее первичной структуре (свидетельство) // Свид. о рег. эл. ресурса, (ОФЭРНиО ИИО ГАН РАО) К® 15769 от 20.05.2010. Бюлл. «Хроники объед. фонда эл. ресурсов «Наука и образование» 2010. №5. С. 27.

52. Тулупъев А.А., Великодная О.И., Филъченков А.А. Программа для поддержки синтеза наборов фрагментов знаний с согласованными оценками вероятностей для формирования алгебраической байесовской сети (свидетельство). Гос. рег. № 50201151353 от 27.10.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) № 17531 от 26.10.2011. Бюлл. «Хроники объед. фонда эл. ресурсов «Наука и образование». 2011. X® 10(29). С. 20.

53. Тулупъев А.Л., Пинский М.Я., Филъченков А.А. База данных для хранения алгебраических байесовских сетей (свидетельство). Гос. рег. Х= 50201151352 от 27.10.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) Х= 17532 от 26.10.2011. Бюлл. «Хроники объед. фонда эл. ресурсов «Наука и образование». 2011. Xе 10(29). С. 20—21.

54. Тулупъев А.Л., Пинский М.Я., филъченков А.А. Графический web-интерфейс пользователя для хранения алгебраических байесовских сетей (свидетельство). Гос. рег. № 50201151351 от 27.10.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) Х= 17533 от

26.10.2011. Бюлл. «Хроники объед. фонда эл. ресурсов «Наука и образование». 2011. Xе 10(29). С. 21.

55. Филъченков А.А., Тулупъев А.Л. Алгоритм построения родительского графа снизу-вверх. Гос. рег. Х= 50201151517 от 07.12.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) Х= 17660 от 07.12.2011. Бюлл. «Хроники объед. фонда эл. ресурсов «Наука и образование». 2011. Х= 12(31). С. 7.

56. Филъченков А.А., Тулупъев А.Л. Алгоритм выявления ацикличности первичной структуры алгебраических байесовских сетей на основе анализа их четвертичной структуры. Гос. рег. X* 50201151516 от 07.12.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) Xs 17661 от 07.12.2011. Бюлл. «Хроники объед. фонда эл. ресурсов «Наука и образование». 2011. X» 12(31). С. 7.

57. Филъченков А.А., Тулупъев А.Л. Алгоритм построения родительского графа при помощи потомков. Гос. рег. Х= 50201151515 от 07.12.2011 (ЦИТиС). Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) Х= 17662 от 07.12.2011. Бюлл. «Хроники объед. фонда эл. ресурсов «Наука и образование». 2011. Xs 12(31). С. 7-8.

58. Тулупъев А.Л., Филъченков А.А., Алексеев А.М. Генератор HTML-таблиц по обобщенному правилу modusponens в вероятностной логике (скалярные ограничения). Гос. рег. Х850201250632 от 16.05.2012 (ЦИТиС) Свид. о рег. эл. ресурса, (ОФЭРНиО ИНИМ ГАН РАО) № 18300 от

16.05.2012. Бюлл. «Хроники объед. фонда эл. ресурсов «Наука и образование». 2012. Х= 5(36). С. 18.

Подписано в печать 11.11.2013 г. Формат А5. Цифровая печать. Заказ 15/109. Объем 1 п.л. Тираж 100 экз. Отпечатано в ЦОП «Копировальный центр «Василеостровский» 199000, Россия, г. Санкт-Петербург, В.О., 6-я линия, д. 29. тел. (812) 702-80-90, факс: 328-61-84 e-mail: vs@copy.spb.ru

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный универститет»

Федеральное государственное бюджетное учреждение науки Санкт-Петербургский институт информатики и автоматизации Российской академии наук

На правах рукописи

04201450093

ФИЛЬЧЕНКОВ Андрей Александрович

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

Специальность 05.13.17 — Теоретические основы информатики

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель

доктор физико-математических наук, доцент ТУЛУПЬЕВ Александр Львович

Санкт-Петербург 2013

Оглавление

Введение........................................................................... 3

Глава 1. Структурный подход в моделировании знаний с неопределенностью. 17

Введение..............................................................................................................................17

§1.1. Моделирование неопределенности знаний с помощью мер истинности 18

§ 1.2. Вероятностные графические модели в искусственном интеллекте________33

§ 1.3. Деревья смежности в представлении систем данных и знаний................51

§1.4. Проблемы машинного обучения в искусственном интеллекте..................65

Выводы по главе..............................................................................................................76

Глава 2. Основы теории алгебраических байесовских сетей.................... 78

Введение............................................................... 78

§ 2.1. Элементы логико-вероятностного подхода............................ 79

§ 2.2. Системы графов и гиперграфов....................................... 90

§ 2.3. Фрагмент знаний АБС................................................. 100

§ 2.4. АБС и глобальный вывод в них....................................... 118

Выводы по главе....................................................... 133

Глава 3. Глобальные структуры алгебраической байесовской сети............. 134

Введение............................................................... 134

§3.1. Минимальные графы смежности...................................... 134

§ 3.2. Связность и ацикличность минимального графа смежности......... 148

§ 3.3. Структура множества минимальных графов смежности.............. 173

§ 3.4. Машинное обучение графов смежности............................... 200

Выводы по главе.......................................................252

Глава 4- Комплекс программ для вычислительных экспериментов........................255

Введение..............................................................................................................................255

§4.1. Состав комплекса программ......................................................................................255

§ 4.2. Основные элементы представления данных......................................................259

§ 4.3. Реализация машинного обучения вторичной структуры АБС................263

§ 4.4. Руководство пользователя и примеры.................................285

Выводы по главе.......................................................300

Заключение........................................................................304

Литература........................................................................ 306

Список иллюстраций.............................................................. 338

Введение

Актуальность темы. Д.А. Поспелов и В.Н. Захаров относили к интеллектуальным методам и технологиям управления в том числе мягкие вычисления, распределенный искусственный интеллект и методы и технологии инженерии знаний и рассуждений на знаниях. Вероятностные графические модели (ВГМ) как область искусственного интеллекта (ИИ) можно отнести к выделенным категориям. Для моделей этого класса общим является локализация вычислений, основанная на принципе декомпозиции и предположениях об условной независимости. ВГМ представляют собой граф, узлам которого приписаны случайные элементы, а ребра определенным образом отображают зависимости между ними.

Алгебраические байесовские сети (АБС), предложенные В.И. Городецким, представляют собой логико-вероятностную графическую модель, опирающуюся на логико-вероятностный подход в интерпретации, выдвинутой Н. Нильссоном для теоретических основ и приложений ИИ. Ключевым отличием АБС является представление неопределенности, в том числе, через интервальные оценки вероятности истинности пропозициональных формул. Проблема представления неопределенности знаний освещалась в работах В.Н. Вагина, A.C. Нариньяни, Г.С. Осипова, Д.А. Поспелова, В.Б. Тарасова, Н.Г. Ярушкиной, A. Dempster, D. Dubois, J. Pearl, R. Fagin, J. Halpern, K. Korb, H. Prade, G. Shafer, L. Zadeh. и многих других.

Теория ВГМ нуждается в моделях, методах и алгоритмах машинного (автоматического) обучения1, в частности, автоматического синтеза глобальных структур таких моделей и автоматического построения оценок их параметров по исходным данным. Комплексная проблема глобального обучения АБС заключается в алгоритмизации синтеза глобальных структур АБС. Среди них выделяют первичную структуру, представляющую собой набор максимальных по включению фрагментов знаний (ФЗ), и вторичную структуру, в данной работе рассматриваемую как граф, построенный над элементами первичной структуры и обладающий особым свойством магистральной связности.

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

Обоснование актуальности исследований также содержит формальную сторону: тема настоящего диссертационного исследования ассоциирована с пунктом 35 «Когнитивные системы и технологии, ..., искусственный интеллект, ..., принятие решений при многих критериях» Программы фундаментальных научных исследований государственных академий наук на 2013-2020 годы (утверждена Распоряжением Правительства РФ от 03.12.2012 г. № 2237-р) в части «теоретические и технологические основы, алгоритмическое обеспечение и

1 Машинное обучение — одна из областей ИИ, связанная с разработкой моделей и алгоритмов, позволяющих вычислительной машине делать предсказания, основываясь на примерах или предыдущем опыте-[-1-70] - - - --------------------- - - - ---- —--

программный инструментарий вероятностных графических моделей, логико-вероятностных графических моделей, ... ».

Степень разработанности темы. В работах A.A. Тулупьева в качестве вторичной структуры АБС рассматриваются деревья смежности, для которых были предложены алгоритмы глобального логико-вероятностного вывода и эффективного поддержания глобальной непротиворечивости. Также в них был предложен подход к устранению отдельных простых циклов графа смежности, и, совместно с соавторами (в первую очередь, с соискателем A.A. Фильченковым) — подход к синтезу множества минимальных графов смежности. A.B. Сироткин формализовал понятие магистральной связности как специфического свойства графов смежности. В.В. Опарин выдвинул идею одного из вариантов синтеза минимального графа смежности, сводящуюся к использованию жадного алгоритма [36].

Исследованиями по выявлению и устранению цикличности гиперграфов занимались В.В. Быкова, С. 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) реализовать описанные алгоритмы синтеза вторичной структуры АБС, а также анализа и преобразования первичной структуры в прототипе комплекса программ для вычислительных экспериментов.

Методология и методы исследования. Работа носит теоретический характер и выполнена преимущественно в рамках теории конечных графов, в том числе теории гиперграфов и ее приложений в информатике: Работа опирается_на методологию дедуктивного и индук-~

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

Научная новизна. Все результаты, выдвигаемые на защиту, являются новыми.

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

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

первичной структуре, над которой существует дерево смежности, как известными прежде, так и предложенными в диссертационном исследовании методами.

Разработаны программные компоненты, дополняющие существующий комплекс программ для работы с АБС и реализующие алгоритмы синтеза вторичной структуры АБС, алгоритмы выявления существования дерева смежности над заданной первичной структурой АБС и ее преобразования к структуре, над которой существует дерево смежности.

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

Результаты диссертационного исследования докладывались и обсуждались на следующих научных мероприятиях:

1) Научная сессия НИЯУ МИФИ-2011 (1-5 февраля 2011 г., Москва);

2) VI Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (16-19 мая 2011 г., Коломна);

3) VII Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России (ИБРР-2011)» (2628 октября 2011 г., Санкт-Петербург);

4) VI Международная научно-практическая конференция «Современные информационные технологии и IT-образование» (12-14 декабря 2011 г., Москва);

5) Научная сессия НИЯУ МИФИ-2012 (30 января-4 февраля 2012 г., Москва);

6) Всероссийская научная конференция по проблемам информатики СПИСОК-2012 (25-27 апреля 2012 г., Санкт-Петербург);

7) VI Международная научно-техническая конференция молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем» (21—24 мая 2012 г., Пенза);

8) XV Международная конференция по мягким вычислениям и измерениям (SCM'2012) (25-27 июня 2012 г., Санкт-Петербург);

9) 1-й Международный симпозиум «Гибридные и синергетические интеллектуальные системы: теория и практика» (29 июня - 2 июля 2012 г., Калининград);

10) The 6th Russian Summer School in Information Retrieval (RuSSIR 2012) (August 6-10, 2012. Yaroslavl, Russia);

11) 35-я конференция молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (19-25 августа 2012 г., Петрозаводск);

12) 5-я российская мультиконференция по проблемам управления/конференция «Информационные технологии в управлении-2012» (ИТУ-2012) (9-11 октября 2012 г., Санкт-Петербург);

13) Юбилейная XIII Санкт-Петербургская международная конференция «Региональная информатика (РИ-2012)» (24-26 октября 2012 г., Санкт-Петербург);

14) Международная (44-я Всероссийская) молодежная школа-конференция «Современные проблемы информатики-2013) (27 января - 2 февраля 2013 г., Екатеринбург);

15) Научная сессия НИЯУ МИФИ-2013 (1-6 февраля 2013 г., Москва);

16) Всероссийская научная конференция по проблемам информатики СПИСОК-2013 (23-26 апреля 2013 г., Санкт-Петербург).

Кроме того, результаты диссертационного исследования докладывались на Санкт-Петербургском городском научном семинаре «Информатика и компьютерные технологии» в 2013 году и на заседании Ученого совета СПИИРАН в 2013 году.

Исследования по тематике диссертации были поддержаны:

1) грантом РФФИ, проект № 09-01-00861-а «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью»,

2) грантом РФФИ, проект № 12-01-00945-а «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью»,

3) грантом Правительства Санкт-Петербурга для победителей конкурса грантов Санкт-Петербурга для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2010 г., № 2.1/03-06/018,

4) грантом РФФИ, проект 12-01-31202 мол_а «Развитие теории графов смежности для автоматического обучения баз знаний

с неопределенностью на основе алгебраических байесовских сетей»,

5) грантом РФФИ, проект 12-01-16030-моб_з_рос «Косвенные признаки цикличности вторичной структуры алгебраической байесовской сети» для представления на научном мероприятии «1-й Международный симпозиум "Гибридные и синергетические интеллектуальные системы: теория и практика (ГиСИС'12)"».

Соискатель является руководителем проектов №№ 3-5.

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

— «Логико-вероятностный подход и его обобщения в моделировании, обработке и обучении баз фрагментов знаний с неопределенностью в интеллектуальных системах», шифр ВЫе1;-2008, номер государственной регистрации 01200852455,

— «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероят-

ностной неопределенностью», номер государственной регистрации 01200963057,

— «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», номер государственной регистрации 01201259408.

Полученные результаты могут использоваться в учебн