Введение 4
1. Основные объекты и результаты теории алгебраических
байесовских сетей 8
1.1. Элементы глобальных структур 8
1.2. Классификация сепараторов 13
1.3. Схема алгоритмов синтеза подмножеств МГС 13
1.4. Обозначения, используемые в листингах алгоритмов . . 16
2. Описание ранее разработанных алгоритмов 18
2.1. МК-алгоритмы 18
2.2. Алгоритм сборки 23
3. Описание инкрементальных и декрементальных алгоритмов 25
3.1. Инкрементальные алгоритмы 26
3.2. Декрементальные алгоритмы 28
4. Статистическая оценка сложности алгоритмов 33
4.1. Схема проведения экспериментов 33
4.2. Результаты 33
5. Система анализа и синтеза 37
5.1. Архитектура 37
5.2. Визуализация 39
Заключение 41
Список литературы
Актуальность темы исследования. В 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#,
состоящая из различных компонент и имеющая разнообразную функциональность. Функциональность данной программного комплекса покрывает большую часть операций, существующих на данных момент
для синтеза ММГС. Данная генерация представляет научный интерес
и даст отличную возможность при реализации глобального вывода.
Кроме того, вышеприведенные результаты позволят интегрировать
воедино реализации алгоритмов представления и обработки знаний с
неопределенностью на основе байесовских сетей доверия.
Перспективными направлениями дальнейших исследований являются направления, связанные с дальнейшей оптимизацией генерации
множества минимальных графов смежности, а также поиска минимальных графов смежности, обладающих оптимальными численными характеристиками для проведения глобального логико-вероятностного вывода.
