Актуальность темы исследования. В 1993 году В.И. Городецкий ввел понятие теории алгебраических байесовских сетей (АБС), которая является экземпляром класса вероятностных графических моделей (ВГМ) [9,22,23,30–32].
АБС представлена в виде ненаправленного графа, вершины которого являются фрагментами знаний [8]. Существуют две основные задачи
в рамках АБС: проведение логико-вероятностного вывода [7, 10, 21, 24,
25,28,29] и генерация глобальных структур.
Структурный анализ изучает алгоритмы генерации глобальных
структур: первичной, вторичной, третичной и четвертичной [10]. Результаты предыдущих исследований, посвященных первичной структуре, предложены в [14,17,18]. Синтез вторичной структуры осуществляется и в настоящее время. Проделанную работу по вторичной структуре можно изучить в [6,20]. Генерация множества вторичной структуры, или множества минимальных графов смежности (ММГС), образует класс независимых алгоритмов [16, 19, 28]. Выделение единственной
структуры из такого множества может производиться на основе численных характеристик логико-вероятностного вывода. Также исследования в данный момент ведутся и над третичной [13] и четвертичной
структурами [17,20]. Представление по данным структурам можно получить в [27].
Объектом исследования выступает алгебраическая байесовская
сеть, а предметом исследования — генерация множества минимальных графов смежности в данной теории.
Целью данной выпускной квалификационной работы является ускорение автоматизации синтеза множества вторичной структуры. Для достижения данной цели необходимо решить следующие
задачи:
1. Перенос программных достижений на язык C#, касающихся алгоритмов синтеза ММГС.
42. Разработка инкрементальных алгоритмов генерации ММГС, доказательство их корректности и эффективности, а также предоставление реализации алгоритмов на языке C#.
3. Осуществление визуализации полученного множества.
Методы исследования. Для решения поставленных задач в данной области понадобилось изучить методические материалы, поставить
проблему, проанализировать ее, спроектировать несколько возможных
вариантов решения. Затем были выбраны подходящие средства и технологии программирования, связанные с языком реализации (C#), средой разработки (Visual Studio), сервисом для совместной разработки
(BitBucket). После чего стало необходимым провести тестовые случаи
и статистические эксперименты с целью обоснования корректности и
эффективности полученного решения. В качестве методов решения используются комбинаторика, теория графов, методы объектно-ориентированного программирования (ООП), эмпирические (постановка и проведение статистических экспериментов) и теоретические методы (анализ предыдущих результатов, синтез и формализация разработанных
алгоритмов).
Научная новизна. В данной выпускной квалификационной бакалаврской работе формализованы и исследованы новые инкрементальные алгоритмы синтеза множества минимальных графов смежности,
что отличает указанный способ генерации от предыдущих вариантов
и позволяет с его помощью быстро создавать множество вторичной
структуры в ситуации постоянного изменения первичной структуры.
В настоящей работе были представлены базовые определения глобальных вторичных структур и ММГС, приведены существующие алгоритмы генерации необходимого множества, описана архитектура полученного программного комплекса с диаграммами написанных классов,
а также приведены примеры работы вышеописанных алгоритмов.
В результате проделанной работы реализована библиотека на C#,
состоящая из различных компонент и имеющая разнообразную функциональность. Функциональность данной программного комплекса покрывает большую часть операций, существующих на данных момент
для синтеза ММГС. Данная генерация представляет научный интерес
и даст отличную возможность при реализации глобального вывода.
Кроме того, вышеприведенные результаты позволят интегрировать
воедино реализации алгоритмов представления и обработки знаний с
неопределенностью на основе байесовских сетей доверия.
Перспективными направлениями дальнейших исследований являются направления, связанные с дальнейшей оптимизацией генерации
множества минимальных графов смежности, а также поиска минимальных графов смежности, обладающих оптимальными численными характеристиками для проведения глобального логико-вероятностного вывода.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
