Введение 5
1. Обзорная часть 7
1.1. Введение
1.2. Актуальность работы
1.3. Цели и задачи
1.4. Средства разработки
1.5. Выводы по главе
2. Определения и обозначения 11
2.1. Введение
2.2. Используемые определения и понятия . . . . . . . . . . . 11
2.3. Используемые в листингах алгоритмов обозначения . . . 12
2.4. Выводы по главе
3. Инкрементальные алгоритмы синтеза 15
3.1. Введение
3.2. Инкрементальное добавление вершины в третичную структуру
3.3. Декрементальное удаление вершины из третичной структуры
3.4. Инкрементальное добавление вершины в четвертичную
структуру
3.5. Декрементальное удаление вершины из четвертичной структуры
3.6. Выводы по главе
4. Руководство пользователя 37
4.1. Введение
4.2. Описание программной реализации
4.3. Примеры визуализации работы алгоритмов
4.4. Выводы по главе
3Заключение 53
Список литературы
Алгебраические байесовские сети (АБС), представляющие собой разновидность графических вероятностных моделей [29, 1], на данный момент активно исследуются с точки зрения автоматического синтеза глобальных структур таких моделей [26].
Среди глобальных структур АБС получили формальное определение и рассматриваются первичная, вторичная, третичная и четвертичная. Проблема синтеза вторичной структуры, представленной в виде минимального графа смежности, по первичной, рассматривается в [26].
Несмотря на то, что в данный момент для операций с алгебраической байесовской сетью используют ее вторичную глобальную структуру, третичная также применяется как для генерации случайного минимального графа смежности, так и для порождения всего множества
минимальных графов смежности [20].
В данной работе рассматривается проблема инкрементализации синтеза третичной и четвертичной структур, а именно, исследуется возможность перестроить данные структуры при добавлении новой вершины в первичную, вместо того, чтобы их синтезировать по всему получившемуся набору заново.
Настоящая выпускная квалификационная работа бакалавра является проектной, то есть выполняется совместно с коллегами (Левенцом Даниилом Григорьевичем, Березиным Алексеем Ивановичем), кроме того, тесно связана с ВКР Мальчевской Екатерины Андреевны. Проект представляет собой комплекс программ по синтезу, анализу и визуализации вторичной структуры АБС на платформе .NET с использованием языка C# и свободно распространяемой библиотеки GraphSharp.
Комплекс программ позволяет синтезировать все глобальные структуры алгебраической байесовской сети по набору вершин, добавлять и удалять вершины, изменяя при этом соответствующим образом все структуры, а также генерировать все множество минимальных графов смежности.
Эта работа является частью более широких инициативных проектов, выполняющихся в лаборатории теоретических и междисциплинарных основ информатики СПИИРАН под руководством А.Л. Тулупьева; кроме того, разработки были частично поддержаны грантами РФФИ 15-01-09001-a — «Комбинированный логико-вероятностный графический подход к представлению и обработке систем знаний с неопределенностью: алгебраические байесовские сети и родственные модели», 12-01-00945-а — «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», 09-01-00861-а —«Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью», а также проектом по ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002–2006 годы», 2006-РИ-19.0/001/211, Государственный контракт от «28» февраля 2006 г., № 02.442.11.7289, «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логиковероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой».
Поставленная цель работы — инкрементализация третичной и четвертичной структур алгебраических байесовских сетей — была достигнута. В ходе выполнения выпускной квалификационной работы бакалавра были разработаны 4 алгоритма — добавления и удаления вершин в третичную и четвертичную структуры АБС. Каждый из алгоритмов был протестирован и реализован в рамках библиотеки, интегрированной в комплекс программ по синтезу и анализу вторичной структуры алгебраических байесовских сетей. Кроме того, были доказаны 4 теоремы о корректности вышеупомянутых алгоритмов.
По теме работы была принята к публикации статья на конференцию IITI’16 (список SCOPUS), кроме того часть исследований была представлена на СПИСОК’16
Помощь студентам и аспирантам в выполнении работ от наших партнеров
