Введение 5
1. Алгебраическая байесовская сеть: автоматизация вывода 8
1.1. Введение 8
1.2. Виды логико-вероятностного вывода 9
1.3. Библиотеки логико-вероятностного вывода 12
1.4. Модернизация комплекса программ 13
1.5. Выводы по главе 13
2. Теоретическая основа проекта 15
2.1. Введение 15
2.2. Модель ФЗ 15
2.3. Алгоритмизация логико-вероятностного вывода 20
2.4. Существующие программные реализации 35
2.5. Выводы по главе 38
3. Архитектура разработанного программного комплекса 39
3.1. Введение 39
3.2. Особенности наследования компонентов в системе .... 39
3.3. Структура создания и хранения ФЗ ABN 42
3.4. Структуры локального-логико-вероятностного вывода и
вспомогательные структуры 43
3.5. Выводы по главе 47
4. Программная реализация 48
4.1. Введение 48
4.2. Примеры работы программного комплекса. Проверка и
поддержание непротиворечивости 48
4.3. Примеры работы программного комплекса. Априорный
вывод 50
4.4. Примеры работы программного комплекса. Апостериорный вывод 53
4.5. Выводы по главе 61
Заключение 63
Список литературы 66
Актуальность темы. Одним из направлений современной информатики является обработка знаний с неопределенностью и изучение вероятностных графических моделей (ВГМ) [20, 14, 23]. Алгебраические байесовские сети (АБС) [8, 11] являются одним из классов ВГМ. Они представляют собой ненаправленные графы с идеалами конъюнктов в узлах. Конъюнкты, как и другие формулы, задаются над некоторым фиксированным алфавитом. При этом конъюнктам приписана скалярная или интервальная оценка вероятности истинности. Следуя [20, 23], будем называть идеалы конъюнктов с оценками вероятности фрагментами знаний (ФЗ).
Понятие алгебраических байесовских сетей было введено В.И. Городецким в 1993 году. С того момента теория существенно развилась, написаны работы, развивающие, уточняющие и дополняющие срез теории АБС, связанный со структурными представлениями, например первичными и вторичными структурами [2, 24]. Также были написаны работы, рассматривающие и развивающие подходы к логико-вероятностному выводу в АБС (поддержание непротиворечивости, априорный вывод, апостериорный вывод) [6, 5, 13, 4, 7].
Были разработаны и реализованы программные комплексы, базирующиеся на соответствующей теории. В 2009 году была разработана java-библиотека AlgBN Modeler j.v.01 [19] для работы с алгебраическими байесовскими сетями. Она позволяет хранить фрагменты знаний, изменять их, осуществлять возможные переходы от одних фрагментов знаний к другим. С помощью надстроек над этой библиотекой Algebraic Bayesian Networks Inferrer и Algebraic Bayesian Networks Propagator [18,
17] поддерживаются непротиворечивость фрагмента знаний, локальный априорный и апостериорные выводы, то есть пропагация детерминированных, стохастических и неточных свидетельств, а также некоторые виды глобального логико-вероятностного вывода. В 2011 году была разработана библиотека AlgBN KPB Reconciler cpp.v.01 [21] на Cd—+, которая также реализует функциональность, необходимую для работы с АБС, однако в данной ВКРб используются другие принципы построения структур классов и интерфейсов.
С одной стороны, по причине непрерывного развития и усовершенствования теории и появления матрично-векторных подходов к проведению логико-вероятностного вывода, с другой - из-за необходимости усовершенствования подходов, использовавшихся в уже имеющихся программных реализациях, возникла потребность в программном комплексе, который агрегирует ранее полученные результаты. В следствии чего было решено разработать библиотеку для локального логико-вероятностного вывода в АБС на C#, в рамках объемлющего проекта, с возможностью дальнейшей интеграции ее с другими разработками проекта, относящимися к структурному срезу теории АБС.
Объектом исследования являются алгебраические байесовские сети, а предметом исследования - локальный логико-вероятностный вывод в АБС с использованием матрично-векторных алгоритмов.
Целью данной выпускной квалификационной работы является автоматизация локального логико-вероятностного вывода в алгебраических байесовских сетях, включающего в себя проверку непротиворечивости предварительно созданного ФЗ, решение задачи локального априорного вывода и двух задач локального априорного вывода в АБС. Для достижения поставленной цели были сформированы задачи:
1) развить формализацию локального логико-вероятностного вывода для альтернативных моделей ФЗ;
2) реализация ФЗ и машин вывода на языке C#;
3) разработка примеров и документации.
Апробация результатов исследования. Результаты исследования были представлены на 1-ой Международной научной конференции «Интеллектуальные информационные технологии в технике и на производстве» и на Всероссийской научной конференции по проблемам информатики СПИСОК-2016.
Публикации. По теме выпускной квалификационной работы было подготовлено 5 публикаций, 4 из них были приняты к публикации.
Эта работа является частью более широких инициативных проектов, выполняющихся в лаборатории теоретических и междисциплинарных основ информатики СПИ- ИРАН под руководством А.Л. Тулупьева; кроме того, разработки были частично поддержаны грантами РФФИ 15-01-09001-a — «Комбинированный логико-вероятностный графический подход к представлению и обработке систем знаний с неопределенностью: алгебраические байесовские сети и родственные модели», 12-01-00945-а — «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», 09-01-00861-а —«Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью», а также проектом по ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы», 2006-РИ-19.0/001/211, Государственный контракт от «28» февраля 2006 г., № 02.442.11.7289, «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логико-вероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой».
В ходе работы над выпускной квалификационной работой бакалавра была достигнута основная цель - реализована библиотека на C#, производящая локальный логико-вероятностный вывод в АБС. Она состоит из структуры, создающей ФЗ и свидетельства, построенные над разными множествами, с различными типами оценок вероятности, машин вывода, осуществляющих решение задач априорного и апостериорного выводов и вспомогательных классов.
Все задачи были выполнены, получены следующие результаты:
• доказаны две теоремы, формализующие задачи апостериорный вывод для фрагментов знаний, заданных над идеалом дизъюнктов;
• реализованы ФЗ и машины вывода на языке C#;
• разработаны примеры и документация.
Результаты вошли в 4 публикации:
1. Золотин А.А., Мальчевская Е.А. Матрично-векторные алгоритмы локального апостериорного вывода в алгебраических байесовских сетях над идеалами дизъюнктов // Материалы международной конференции по мягким вычислениям и измерениям (в печати)
2. Zolotin A.A., Malchevskaia E.A. Matrix-Vector Algorithms of Local Posteriori Inference in Algebraic Bayesian Networks on Ideal of Disjuncts // International Conference on Soft Computing and Measurements (in press)
3. Mal’chevskaya E.A., Berezin A.I., Zolotin A.A., Tulupyev A.L. Algebraic Bayesian Networks: Local Probabilistic-Logic Inference Machine Architecture and Set of Minimal Joint Graphs //1st International Scientific Conference «Intelligent information technologies for industry» (in press)
4. Мальчевская Е.А., Золотин А.А. Логико-вероятностный вывод в АБС: архитектура и примеры использования программного комплекса на языке C# // 3-я Всероссийская Поспеловская конференция с международным участием «Гибридные и синергетические интеллектуальные системы» (в печати)
Результаты были представлены на двух конференциях: 1-ой Международной научной конференции «Интеллектуальные информационные технологии в технике и на производстве» и Всероссийской научной конференции по проблемам информатики СПИСОК-2016.
Была подана заявка на регистрацию программы для ЭВМ: Мальчевская Е.А., Тулупьев А.Л. Система представления фрагментов знаний алгебраических байесовских сетей Algebraic Bayesian Networks Knowledge Patterns Modeler, Version 01 for CSharp (AlgBN KP Modeler cs.v.01).
Работа выполнялась под руководством А.Л. Тулупьева, на базе лаборатории теоретических и междисциплинарных проблем информатики СПИИРАН; кроме того, разработки были частично поддержаны грантами РФФИ 15-01-09001-a — «Комбинированный логико-вероятностный графический подход к представлению и обработке систем знаний с неопределенностью: алгебраические байесовские сети и родственные модели», 12-01-00945-а — «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», 09-01-00861-а —«Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью», а также проектом по ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы», 2006-РИ-19.0/001/211, Государственный контракт от «28» февраля 2006 г., № 02.442.11.7289, «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логико-вероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой».
Полученные результаты позволяют в будущем развить функциональность данной библиотеки, реализовывать глобальный логико-вероятностный вывод, а также интегрироваться с другими подпроектами, которые связаны со структурной компонентой библиотеки.