Санкт-Петербургский государственный университет
Направление «Математическое обеспечение и администрирование
информационных систем»
Профиль «Математические основы информатики»
Екатерина Андреевна Мальчевская
Алгебраические байесовские сети: система
логико-вероятностного вывода на основе
матрично-векторных алгоритмов
Бакалаврская работа
Научный руководитель:
проф. каф. инф., д. ф.-м. н., доц. Тулупьев А. Л.
Рецензент:
доцент НИУ ВШЭ СПб, к.ф.-м.н. Сироткин А. В.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Mathematical Software and Information Systems Administration
Mathematical foundations of computer science
Ekaterina Malchevskaia
Algebraic Bayesian networks:
probabilistic-logic inference system based on
matrix-vector algorithms
Bachelor’s Thesis
Scientific supervisor:
Professor, PhD, Associate Professor Tulupyev A. L.
Reviewer:
Associate Professor, PhD Sirotkin A. V.
Saint-Petersburg
2016
Оглавление
Введение
5
1. Алгебраическая байесовская сеть: автоматизация
да
1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Виды логико-вероятностного вывода . . . . . . . . .
1.3. Библиотеки логико-вероятностного вывода . . . . .
1.4. Модернизация комплекса программ . . . . . . . . .
1.5. Выводы по главе . . . . . . . . . . . . . . . . . . . . .
2. Теоретическая основа проекта
2.1. Введение . . . . . . . . . . . . . . . . . . . . . . .
2.2. Модель ФЗ . . . . . . . . . . . . . . . . . . . . . .
2.3. Алгоритмизация логико-вероятностного вывода
2.4. Существующие программные реализации . . . .
2.5. Выводы по главе . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
выво.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
8
9
12
13
13
.
.
.
.
.
15
15
15
20
35
38
3. Архитектура разработанного программного комплекса
3.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Особенности наследования компонентов в системе . . . .
3.3. Структура создания и хранения ФЗ ABN . . . . . . . . .
3.4. Структуры локального-логико-вероятностного вывода и
вспомогательные структуры . . . . . . . . . . . . . . . . .
3.5. Выводы по главе . . . . . . . . . . . . . . . . . . . . . . . .
39
39
39
42
4. Программная реализация
4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Примеры работы программного комплекса. Проверка и
поддержание непротиворечивости . . . . . . . . . . . . . .
4.3. Примеры работы программного комплекса. Априорный
вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
48
3
43
47
48
50
4.4. Примеры работы программного комплекса. Апостериорный вывод . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Выводы по главе . . . . . . . . . . . . . . . . . . . . . . . .
53
61
Заключение
63
Список литературы
66
4
Введение
Актуальность темы. Одним из направлений современной информатики является обработка знаний с неопределенностью и изучение вероятностных графических моделей (ВГМ) [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] на
C++, которая также реализует функциональность, необходимую для
5
работы с АБС, однако в данной ВКРб используются другие принципы
построения структур классов и интерфейсов.
С одной стороны, по причине непрерывного развития и усовершенствования теории и появления матрично-векторных подходов к проведению логико-вероятностного вывода, с другой – из-за необходимости усовершенствования подходов, использовавшихся в уже имеющихся
программных реализациях, возникла потребность в программном комплексе, который агрегирует ранее полученные результаты. В следствии
чего было решено разработать библиотеку для локального логико-вероятностного вывода в АБС на C#, в рамках объемлющего проекта,
с возможностью дальнейшей интеграции ее с другими разработками
проекта, относящимися к структурному срезу теории АБС.
Объектом исследования являются алгебраические байесовские сети,
а предметом исследования – локальный логико-вероятностный вывод в
АБС с использованием матрично-векторных алгоритмов.
Целью данной выпускной квалификационной работы является автоматизация локального логико-вероятностного вывода в алгебраических
байесовских сетях, включающего в себя проверку непротиворечивости
предварительно созданого ФЗ, решение задачи локального априорного вывода и двух задач локального априорного вывода в АБС. Для
достижения поставленной цели были сформированы задачи:
1) развить формализацию локального логико-вероятностного вывода для альтернативных моделей ФЗ;
2) реализация ФЗ и машин вывода на языке C#;
3) разработка примеров и документации.
Апробация результатов исследования. Результаты исследования были представлены на 1-ой Международной научной конференции «Интеллектуальные информационные технологии в технике и на производстве» и на Всероссийской научной конференции по проблемам информатики СПИСОК-2016.
6
Публикации. По теме выпускной квалификационной работы было
подготовлено 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, «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логико-вероятностного
вывода для программных комплексов с байесовской интеллектуальной компонентой».
7
1. Алгебраическая байесовская сеть: автоматизация вывода
1.1. Введение
Рассмотрим ситуацию, когда у нас есть несколько атомарных утверждений и есть эксперты, которые могут охарактеризовать взаимосвязи
данных утверждений. Количеству утверждений соответствует экспоненциальное количество всех возможных взаимосвязей. Выходит, что
при изначально большом количестве утверждений эксперт не сможет
оценить все возможные взаимосвязи. Вероятностные графические модели и, в частности, алгебраические байесовские сети – одно из решений. Мы разбиваем множество всех утверждений на небольшие подмножества, называем их фрагментами знаний (ФЗ), и внутри них описываем все возможные взаимосвязи между элементами подмножества.
Пример подобного ФЗ изображен на Рис. 1.
Рис. 1. Пример ФЗ построенного над A = {x1 , x2 , x3 }.
Множество всех получившихся ФЗ образуют базу фрагментов знаний(БФЗ). Изображение АБС таким образом, как это представлено на
8
Рис. 2, то есть расммотрение сети, как множества ФЗ, мы называем
первичной структурой АБС. Если мы рассмотрим граф смежности, в
котором в качестве узлов будут выступать ФЗ, а ребро между двумя
вершинами будет существовать, если у этих вершин, то есть ФЗ, есть
общие атомы, то такой граф мы назовем вторичной структурой алгебраической байесовской сети. Примеры вторичной структуры алгебраической байесовской сети для АБС, представленной на Рис. 2, изображены на Рис. 3 и на Рис. 4.
Рис. 2. Пример первичной структуры АБС, состоящей из двух ФЗ, построенной над
A = {x1 , x2 , x3 , x4 }.
Рис. 3. Пример вторичной структуры АБС, состоящей из двух ФЗ, построенной над
A = {x1 , x2 , x3 , x4 }.
Для определения степени неопределенности для утверждений и связей между ними мы можем использовать точечные(скалярные) оценки
вероятности или же интервальные. На примере Рис. 5 можно увидеть,
как могут быть заданы скалярные оценки вероятности.
1.2. Виды логико-вероятностного вывода
В качестве способа получения обусловленных данных, при условии
уже имеющихся в АБС, существует апарат логико-вероятностного вы9
Рис. 4. Пример вторичный структуры АБС, состоящей из двух ФЗ, построенной над
A = {x1 , x2 , x3 , x4 }.
Рис. 5. Пример скалярных оценок вероятности заданных над ФЗ, построенного над
A = {x1 , x2 }.
вода. Существует два вида логико-вероятностного вывода: локальный
и глобальный. Локальный вывод рассматривается в пределах одного
конкретного ФЗ, а глобальный затрагивает АБС в целом [8, 12]. В данной работе рассматривается в основном локальный вывод. Локальный
логико-вероятностный вывод в АБС делится на априорный и апостериорный. Целью локального апостериорного логико-вероятностного вывода в АБС является решение двух задач. Разберем каждый вид вывода
подробнее.
Априорный вывод заключается в том, что у нас есть ФЗ с заданными оценками вероятности и у нас есть пропозициональная форму10
ла, вероятность которой мы хотим вычислить, при условии заданных
оценок. Алфавит, над которым задана пропозициональная формула,
должен быть подмножеством алфавита, над которым задан рассматриваемый ФЗ.
Апостериорный вывод состоит в том, что нам приходит какая-то
обуславливающая информация и при решении первой задачи апостериорного вывода мы считаем вероятность того, что такая информация
могла прийти, при условии нашего ФЗ, а в случае решения второй задачи апостериорного вывода мы на основе пришедшего знания должны
пересчитать оценки вероятностей нашего ФЗ.
Для проверки совместимости оценок вероятностей фрагментов знаний используются разные апараты по проверке непротиворечивости
(согласованности). На Рис. 6 приведен пример явно противоречивого
ФЗ. Он оказывается противоречивым вследствии того, что вероятность
атома не может быть меньше, чем вероятность конъюнкции, в которую
входит данный атом. Также стоит отметить, что вероятность пустого
конъюнкта, на изображениях обозначенного как ϵ∧ равна 1, т.к пустой
конъюнкт представляет собой тождественную истину в вероятностной
логике, что не выполняется в примере, изображенном на Рис. 7.
Рис. 6. Пример противоречивого ФЗ (1)
11
Рис. 7. Пример противоречивого ФЗ (2)
1.3. Библиотеки логико-вероятностного вывода
На настоящий момент известны библиотеки для работы с алгебраическими байесовскими сетями, а в частности две библиотеки, написанные на Java и на C++ [19, 21], которые включают в себя формирование
ФЗ различных видов, их обработку, средства для локального априорного и апостериорного вывода и средства для глобального вывода.
Первая библиотека AlgBN Modeler j.v.01 была разработана на Java
в 2009 году [19]. Особенностью данной библиотеки является разделение функциональности хранения фрагментов знаний с инструментами
локального и глобального вывода, что позволяет назвать данную реализацию ФЗ «тонкой». При таком подходе, формирование и хранение
ФЗ независимо от инструментов вывода, которые мы применяем.
Вторая библиотека AlgBN KPB Reconciler cpp.v.01 была разработана на C++ [21]. В реализации данной библиотеки применяется другой подход, который подразумевает объединение средств формирования и обработки фрагментов знаний с инструментами локального вывода. При таком подходе мы можем назвать реализацию ФЗ «толстой».
12
1.4. Модернизация комплекса программ
С 1980-х годов по настоящее время, были опубликованы монографии [8, 11, 20, 14, 23], диссертации [9, 3], статьи на тему алгебраических байесовских сетей и байесовских сетей в целом [16, 15]. Также
развивалось и программное обеспечивание и в связи с этим целью данной работы был перенос и усовершенствование частей библиотеки [19],
отвечающих за формирование, хранение ФЗ, проведение локального
логико-вероятностного вывода, на язык С# и платформу .NET.
Преимуществами реализации библиотеки именно на C# является
то, что это позволит использовать библиотеки для решения задач линейного программирования и еще множество библиотек, реализованных на данной платформе. Также это позволит интегрировать полученные результаты с другой частью библиотеки, связанной с первичными,
вторичными и более сложными структурами АБС.
В разработанной библиотеке основное внимание уделено обеспечению использования особенностей представления бинарных ФЗ как скалярных и интервальных, а скалярных как интервальных и на то, чтобы
реализация соответствовала «тонкой».
Целью данной выпускной квалификационной работы является автоматизация локального логико-вероятностного вывода в алгебраических
байесовских сетях, включающего в себя проверку непротиворечивости
предварительно созданого ФЗ, решение задачи локального априорного вывода и двух задач локального априорного вывода в АБС. Для
достижения поставленной цели были сформированы задачи:
1. развить формализацию локального логико-вероятностного вывода для альтернативных моделей ФЗ;
2. реализация ФЗ и машин вывода на языке C#;
3. разработка примеров и документации.
1.5. Выводы по главе
В данной главе рассмотрены основные понятия, связанные с тео13
рией АБС и локальным логико-вероятностным выводом и его видами.
Упомянуты некоторые существующие программные реализации. Приведена цель и задачи данной выпускной квалификационной работы.
14
2. Теоретическая основа проекта
2.1. Введение
В данной главе введем необходимые математические понятия и определения, которые формально описывают модель ФЗ в алгебраической
байесовской сети и те операции, которые над ней можно выполнять.
Рассмотрим базовые принципы и алгоритмы по работе с локальными
априорным и апостериорным логико-вероятностными выводами. Раскроем и разовьем понятия, относящиеся к логико-вероятностному выводу. В основу дальнейшего изложения взят ряд источников [9, 3, 14, 7].
2.2. Модель ФЗ
2.2.1. ФЗ, построенные над идеалом конъюнктов
Алгебраическая байесовская сеть является одной из моделей, которые представляют данные с неопределенностью, а также вероятностной
графической моделью. Неопределенность возникает вследствие того,
что конъюнктам в узлах фрагментов знаний, из которых состоит АБС,
приписывается некоторая вероятность, степень неточности.
Определение 2.1 [3] Алфавит А = {xi }n−1
i=0 – конечное множество
атомарных пропозициональных формул (атомов). Введем нумерацию
атомов с нуля.
Теперь над атомами из указанного алфавита определим наборы пропозициональных формул.
Определение 2.2 [3] Конъюнкт (цепочка конъюнкций) – это конъюнкция некоторого числа атомарных переменных вида:
xi1 ∧ xi2 ∧ · · · ∧ xik .
Мы можем такие формулы записывать, опустив знаки конъюнций.
Не будем их различать, если это не будет вызывать неоднозначность:
xi1 xi2 · · · xik .
15
Определение 2.3 [3] Идеал конъюнктов (идеал цепочек конъюнкций)
– это множество вида
{xi1 ∧ xi2 ∧ · · · ∧ xik | 0 ≤ i1 < i2 < · · · < ik ≤ n − 1, 0 ≤ k ≤ n}.
Обозначим идеал конъюнктов над алфавитом А, как CA .
Определение 2.4 [3] Каждому конъюнкту xi1 xi2 · · · xik . сопоставим
число
2i1 + 2i2 + · · · + 2ik .
– индекс конъюнкта.
Определение 2.5 [3] Литерал(аргументное место) x̃i обозначает,
что на его месте в формуле может стоять либо xi , либо x̄i .
Определение 2.6 [3] Квант над над алфавитом A = {xi }n−1
i=0 – это
конъюнкция, которая для любого атома алфавита содержит либо
этот атом, либо его отрицание.
Определение 2.7 [3] Множество квантов над алфавитом = {xi }n−1
i=0 :
Q = {x̃i1 x̃i2 · · · x̃ik }.
Для нумерации квантов будем пользоваться методом, аналогичным
нумерации конъюнктов, более подробно о нем можно прочитать в [3].
После введения нумерации можно определить векторы оценок вероятности квантов и конъюнктов соответственно [3]:
p(q0 )
p(q1 )
Pq =
..
.
p(q2n−1 )
16
и
1
p(c1 )
Pc =
..
.
p(c2n−1 )
.
Теперь введем некоторые определения, связанные с видами фрагментов знаний.
Определение 2.8 [3] Фрагмент знаний (ФЗ) со скалярными оценками – это пара вида (C, p), где C – идеал конъюнктов, а p – функция из
C в интервал [0; 1]
Определение 2.9 [3] Фрагмент знаний (ФЗ) с интервальными оценками – это структура вида (C, p), где C – идеал конъюнктов, а p –
функция из C в множество интервалов вида
{[a; b] : a, b ∈ [0; 1], a ≤ b}.
Введем базовые определения непротиворечивости и согласуемости
ФЗ [3].
Определение 2.10 [3] Пусть задан ФЗ со скалярными оценками вероятности (C, p). Мы говорим, что он непротиворечив(согласован),
и обозначаем это как Consistent[(C, p)] тогда и только тогда, когда
существует вероятность pF , заданная над множеством пропозициональных формул F (A)(где A – это алфавит, над которым построен
ФЗ), такая что
∀c ∈ C pF = p(c).
Определение 2.11 [3] Пусть задан ФЗ с интервальными оценками
вероятности (C, p). Мы говорим, что он непротиворечив(согласован),
и обозначаем это как Consistent[(C, p)] тогда и только тогда, когда
для любого конъюнкта c ∈ C и любого ϵ ∈ p(c) найдется функция
pc,ϵ : C → [0, 1] такая, что pc,ϵ = ϵ и (C, pc,ϵ ) – непротиворечивый в
смысле предыдущего определения.
17
Определение 2.12 [3] Пусть задан ФЗ с интервальными оценками
вероятностей (C, p). Мы говорим, что он согласуем тогда и только тогда, когда существует непротиворечивый ФЗ с интервальными
оценками (C, p′ ) такой, что
∀c ∈ C p′ (c) ⊆ p(c).
Введем основные понятия локального апостериорного логико-вероятностного вывода в рамках рассматриваемой модели ФЗ. Для формализации локального логико-вероятностного вывода нам необходимо ввести определение математической модели свидетельства в АБС.
Определение 2.13 [3] Задача локального априорного вывода состоит в том, чтобы на основе непротиворечивого фрагмента знаний построить оценки истинности пропозициональной формулы, заданной
над тем же алфавитом, что и фрагмент знаний.
Определение 2.14 [3] Свидетельство – новые «обусловливающие»
данные, которые поступили во ФЗ, и с учетом которых нам требуется пересмотреть все (или только некоторые) оценки. Для обозначения
свидетельства будут использоваться угловые скобки – ⟨· · ·⟩.
Далее оговорим, что из себя представляют задачи апостериорного
логико-вероятностного вывода.
Определение 2.15 [3] Первая задача апостериорного вывода состоит в том, чтобы оценить вероятность истинности свидетельства
при уже заданных оценках вероятности истинности элементов ФЗ.
Определение 2.16 [3] Вторая задача апостериорного вывода состоит в том, чтобы оценить условные вероятности истинности элементов ФЗ при предположении, что имеет место быть свидетельство.
18
2.2.2. Альтернативные математические модели ФЗ
Вслед за [14] определим две альтернативные математические модели, одна из которых образована над идеалам дизъюнктов, другая – над
множеством квантов.
Определение 2.17 [14] Фрагментом знаний над идеалом дизъюнктов Cd со скалярными оценками вероятности определяется как упорядоченная пара (C∨ , p), где C∨ – идеал дизъюнктов, лежащий в основе
ФЗ, а p – функция на C∨ , задающая скалярные (точечные) оценки вероятностей:
p : C∨ ← [0; 1].
Значения этой функции, упорядоченные по аналогии с конъюнктами, записываются в виде вектора D или Pd . Компоненты вектора
нумеруются с 0 до 2m − 1. Обратим внимание, что нулевой компонент
вектора D0 = 0, так как пустой дизъюнкт соответствует тождественной
лжи.
Определение 2.18 [14] ФЗ над множеством квантов Cq со скалярными оценками вероятности определяется как упорядоченная пара
(Q, p), где Q – множество квантов, лежащее в основе ФЗ, а p – функция на Q, задающая скалярные (точечные) оценки вероятностей:
p : Q ← [0; 1].
Значения этой функции, упорядоченные по аналогии с конъюнктами, записываются в виде вектора Q или Pq . Компоненты вектора
нумеруются с 0 до 2m − 1.
Используя введенные векторные обозначения ФЗ над идеалом дизъюнктов, можно рассмотреть как пару (C∨ , D), состоющую из множества
квантов и вектора скалярных оценок этих дизъюнктов, а ФЗ над множеством квантов как пару (Q, Q), состоящую из множества квантов и
вектора скалярных оценок этих квантов.
19
После введения нумерации можем определить вектор оценок вероятностей дизъюнктов соответственно.
0
p(d1 )
.
Pd =
..
.
p(d2n−1 )
2.3. Алгоритмизация логико-вероятностного вывода
Прежде чем приступить непосредственно к рассмотрению алгоритмов решения задач локального логико-вероятностного вывода, разберем апарат, осуществляющий проверку непротиворечивости вероятностных оценок ФЗ и некоторые понятия с ним связанные.
2.3.1. Поддержание непротиворечивости
Рассмотрим вероятность на ранее введенном множестве всех квантов Q. Запишем требующиеся ограничения в векторном виде:
Pq ≥ 0,
(1, Pq ) = 1.
Вектор 1 – вектор подходящей размерности, состоящий из единиц. В
большинстве случаев, размерность вектора 2n .
Матрица In , упомянутая ранее, имеет чёткую структуру [3], которую
можно описать рекуррентно.
(
)
1 −1
[n−1]
[n]
I1 =
, · · · , In = I1 ⊗ In−1 = I1 ⊗ I1
= I1 .
0 1
При этом выполняется соотношение:
Pq = In × Pc .
Здесь ⊗ кронекерово произведение матриц. Также используется об-
20
ратная матрице In матрица Jn , которая удовлетворяет условию:
(
J1 =
1 1
0 1
Pc = Jn × Pq ,
)
[n−1]
, Jn = J1 ⊗ Jn−1 = J1 ⊗ J1
[n]
= J1 .
Теперь, вслед за [3], сформулируем определения непротиворечивости фрагментов знаний, описанные ранее на матрично-векторном языке.
Определение 2.19 Пусть задан ФЗ со скалярными оценками вероятностей (C, Pc ). мы говорим, что он непротиворечив тогда и только
тогда, когда
In × Pc ≥ 0.
Определение 2.20 Пусть задан ФЗ с интервальными оценками ве+
роятностей (C, P−
c , Pc ). Мы говорим, что он непротиворечив тогда и
только тогда, когда
∀i : 1 ≤ i ≤ 2n − 1
+
∀ϵ : P−
c [i] ≤ ϵ ≤ Pc [i]
+
∃Pc : (P−
c ≤ Pc ≤ Pc ) & (Pc [i] = ϵ) & (In × Pc ≥ 0).
Определение 2.21 Пусть задан ФЗ с интервальными оценками ве+
роятностей (C, P−
c , Pc ). Мы говорим, что он согласуем тогда и только тогда, когда существует непротиворечивый ФЗ с интервальными
−
+
+
оценками (C, P− , P+ ), такой что P−
c ≤ P и P ≤ Pc .
Обоснование приведенных выше рассуждений, дополнительные факты, утверждения и теоремы и примеры приведены в [3].
Далее рассмотрим зависимости, связанные с поддержанием непротиворечивости фрагментов знаний, представленными идеалом дизъюнктов и множеством квантов.
Введем обозначения: вектор 1m – вектор, состоящий из 2m единиц и
вектор 0 – вектор, состоящий из того же числа элементов, причем все
·
будут нулевыми, кроме самого нижнего, который будет равен единице.
21
Определим вектор Pc как вектор, содержащий вероятность каждого
конъюнкта, составленного из отрицаний атомов.
Имеют место соотношения:
1m − Pc = D,
1m − D = Pc .
Определение 2.22 Для ФЗ Cd = (C∨ , D) задание скалярных оценок
считается непротиворечивым, если
ID ≤ 0 .
·
Определение 2.23 Для ФЗ Cq = (Q, Q) задание скалярных оценок
считается непротиворечивым , если
Q ≥ 0,
(Q, 1) = 1.
Доказательства и обоснования приведенных фактов и закономерностей представлено в [14].
2.3.2. Априорный вывод
Рассмотрим локальный априорный вывод над двумя видами ФЗ:
скалярным и интервальным.
Априорный вывод над скалярным ФЗ. Опишем решение задачи априорного вывода для случая ФЗ со скалярными оценками вероятности. Рассмотрим непротиворечивый ФЗ со скалярными оценками
(C, Pc ). Мы можем выразить вероятность произвольной пропозициональной формулы через вероятности квантов, входящих в её СДНФ.
Определение 2.24 Пусть f – произвольная пропозициональная формула, тогда характеристическим вектором формулы f мы будем называть вектор χf , состоящий из 2n элементов, такой, что
22
{
χf [i] =
0, если qi ∈
/ Sf ;
1, если qi ∈ Sf
, где qi обозначает i-й квант, а Sf – множество квантов, содержащихся в СДНФ ф-лы f .
Рассмотрим пропозициональную формулу f , истинность которой
требуется оценить. На основе прежде рассмотренных знаний мы можем сделать вывод, что
p(f ) = (χf , Pq ).
Используя ранее рассмотренные формулы, мы можем перейти от
вектора с вероятностями квантов к вектору с вероятностями конъюнктов и получим
p(f ) = (χf , In × Pc ) = (IT
n × χf , Pc ).
Обозначим Lf = ITn × χf , тогда
p(f ) = (Lf , Pc ).
Априорный вывод над интервальным ФЗ. Перейдем к ФЗ с интервальными оценками вероятности. В данном случае однозначно определить вероятность истинности пропозициональной формулы не удастся, но можно найти максимальную и минимальную оценки:
p− (f ) = min(Lf , Pc ),
D∪E
p(f )+ = max(Lf , Pc ).
D∪E
2.3.3. Апостериорный вывод
В теории АБС рассматриваются три вида свидетельств: детерминированные, стохастические и неточные.
23
Определение 2.25 Детерминированное свидетельство – некоторое
означивание цепочки конъюнкций, рассматриваемое в качестве поступившего свидетельства. Данное свидетельство обозначается ⟨ci , cj ⟩.
Здесь ci , cj – конъюнкты, состоящие из атомов, получивших положительные и отрицательные означивания соответственно.
Определение 2.26 Стохастическое свидетельство – непротиворечивый ФЗ, заданный над C ′ – подыдеале C, со скалярными оценками,
которые определяет вероятности истинности элементов соответствующего подыдеала. Данное свидетельство обозначается ⟨(C ′ , Pc )⟩.
Определение 2.27 Неточное свидетельство – непротиворечивый ФЗ
с C ′ – подыдеале C интервальными оценками, которые определяет
вероятности истинности элементов соответствующего подыдеала.
+
Данное свидетельство обозначается ⟨(C ′ , P−
c , Pc )⟩.
Все рассмотренные выше задачи образуют локальный логико-вероятностный вывод в АБС, который был реализован в программном
комплексе. Также большинство задач ЛВВ сводится к решению задач
линейного программирования(ЛП), то есть поиску минимума и максимума некоторой целевой функции, при заданных органичениях, что
позволяет использовать известные методы решения задач ЛП.
Детерминированное свидетельство и ФЗ со скалярными оценками. Для начала рассмотрим процесс обработки детерминированного свидетельства ⟨i, j⟩, поступившего в ФЗ со скалярными оценками
(C, Pc ).
Определение 2.28 [3] Введем дополнительные обозначения.
(
H+ =
(
H− =
0 0
0 1
0 0
0 1
24
)
,
)
,
(
Ho =
0 0
0 1
)
.
А теперь определим матрицу, как тензорное произведение:
⟨i,j⟩
⟨i,j⟩
⟨i,j⟩
H⟨i,j⟩ = Hn−1 ⊗ Hn−2 ⊗ · · · ⊗ H0 ,
где
⟨i,j⟩
Hk
+
H , если xk входит в ci ;
=
H− , если xk входит в cj ; .
Ho , иначе.
Утверждение 2.3.1 [3] Пусть задан ФЗ со скалярными оценками
(C, Pc ), тогда вероятность истинности свидетельства ⟨i, j⟩ при условии заданных ФЗ может быть вычислена по формуле
p(⟨i, j⟩|(C, Pc )) = (1, H⟨i,j⟩ × Pq ).
Подробное обоснование данного факта можно найти в [3].
Определение 2.29 [3] Пусть имеется свидетельство ⟨ci , cj ⟩, а cj
представляет собой конъюнкт xj1 xj2 · · · xjk , тогда этому свидетельству соответствует пропозициональная формула
q⟨i,j⟩ = ci xj1 xj2 · · · xjk .
Далее рассмотрим вектор, состоящий из условных вероятностей квантов при заданном свидетельстве:
p(q0 |q⟨i,j⟩ )
..
P⟨i,j⟩
=
.
.
q
p(q2n −1 |q⟨i,j⟩ )
25
Теперь воспользуемся определением матрицы H. Вышерассмотренный вектор можно записать в матрично-векторном виде:
⟨i,j⟩
P⟨i,j⟩
× Pq .
q p(⟨ci , cj ⟩) = H
По аналогии построим вектор:
p(c0 |q⟨i,j⟩ )
..
P⟨i,j⟩
=
.
.
c
p(c2n −1 |q⟨i,j⟩ )
⟨i,j⟩
Утверждение 2.3.2 [3] Векторы Pc
ми
⟨i,j⟩
и Pq
связаны соотношения-
P⟨i,j⟩
= Jn × P⟨i,j⟩
c
q ,
P⟨i,j⟩
= In × P⟨i,j⟩
q
c .
Доказательство данного утверждения также приведено в [3].
После ряда преобразований получим :
⟨i,j⟩
P⟨i,j⟩
× In × Pc .
q p(⟨ci , cj ⟩) = Jn × H
Рассмотрим матрицу, которая при фиксированных i и j будет задаваться однозначно:
T⟨i,j⟩ = Jn × H⟨i,j⟩ × In .
Подставим эту матрицу в ранее рассмотренное выражение и получим:
⟨i,j⟩
P⟨i,j⟩
× Pc .
q p(⟨ci , cj ⟩) = T
Теорема 2.1 [3] В случае ФЗ со скалярными оценками решением первой задачи апостериорного вывода для свидетельства ⟨i, j⟩ является
(T⟨i,j⟩ × Pc )[0] .
26
Теорема 2.2 [3] Если p(⟨ci , cj ⟩) ̸= 0, то решение второй задачи апостериорногго вывода в случае детерминированного свидетельства даёт формула:
P⟨i,j⟩
q
1
T⟨i,j⟩ × Pc
⟨i,j⟩
=
T × Pc =
.
(T⟨i,j⟩ × Pc )[0]
(T⟨i,j⟩ × Pc )[0]
Если p(⟨ci , cj ⟩) = 0, то поступившее свидетельство имело вероятность 0, то есть произойти не могло, в этом случае будем говорить, что
свидетельство невероятное.
Детерминированное свидетельство и ФЗ с интервальными оценками. Теперь рассмотрим ФЗ с интервальными оценками вероятно+
сти P−
c и Pc . В этом случае решение первой и второй задач апостериорного вывода для детерминированного свидетельства можно представить как решение серии задач линейного программирования(ЛП).
Рассмотрим первую задачу апостериорного вывода.
Утверждение 2.3.3 [3] Для детерминированного свидетельства ⟨i, j⟩
существует вектор L⟨i,j⟩ такой, что для решения первой задачи апостериорного вывода при заданном свидетельстве и интервальных оценках во фрагменте знаний необходимо решить две задачи линейного
программирования, соответствующие поиску величин:
min{(L⟨i,j⟩ , Pc )},
D∪E
max{(L⟨i,j⟩ , Pc )}.
D∪E
Перейдем ко второй задаче апостериорного вывода. Её решением будут
следующие величины:
min{P⟨i,j⟩
c [i]},
D∪E
max{P⟨i,j⟩
c [i]}.
D∪E
Теорема 2.3 [3] Решением второй задачи локального апостериорного вывода в случае детерминированного свидетельства и ФЗ с интер27
вальными оценками явлляется решение серии задач ЛП по поиску:
min{T⟨i,j⟩ × D},
max{T⟨i,j⟩ × D},
при условиях:
+
⟨i,j⟩
{λP−
, D) = 1} ∪ {λ ≥ 0}.
c ≤ D} ∪ {λPc ≥ D} ∪ {In × D ≥ 0} ∪ {(L
Доказательства обоих вышерассмотренных утверждений приведены
в [3].
Стохастические свидетельства.
Определение 2.30 [3] Пусть задан идеал конъюнктов C, тогда будем использовать обозначение Ac для сужения алфавита A до элементов, над которыми задан C, а Qc , для множества квантов, заданных
над этим алфавитом.
Пусть нам задан ФЗ со скалярными оценками (C, Pc ). И, согласно определению стохастического свидетельства, задан непротиворечивый ФЗ (C ′ , Pac ), такой, что C ′ ⊆ C. Так как (C ′ , Pac ) – непротиворечивый, то на основе оценок вероятностей для конъюнктов Pac , можно
построить оценки вероятности для квантов QC ′ – Paq = I × Pac . Элементы множества QC ′ являются взаимоисключающими, то есть при любом зафиксированном означивании всех атомов истинным будет только один и только один элемент множества QC ′ . Кроме того, каждый
элемент QC ′ можно трактовать как соответствующее детерминированной свидетельство, для ФЗ (C, Pc ). Пользуясь этими свойствами мы
можем формализовать стохастическое свидетельство следующим образом: свидетельство (C ′ , Pac ) – случайный элемент, принимающий значение детерминированных свидетельств, соответствующих элементам
QC ′ с вероятностями Paq . При такой формализации мы можем перейти
к описанию двух задач апостериорного вывода. Так как свидетельство
является случайным элементом, а в качестве решений первой и второй
28
задач апостериорного вывода нужно получить численные значения, то
решениями будем считать соответствующие математические ожидания.
Рассмотрим решение первой задачи апостериорного вывода. Для детерминированного свидетельства ⟨i, j⟩ это (T⟨i,j⟩ × Pc )[0] Нам необходимо уметь сопоставлять индексы множества QC ′ индексам детерминированных свидетельств. Для этого определим вспомогательную функцию
GInd(i, m), где m – это это индекс наибольшего элемента C ′ в алфавите
A, i – идекс конъюнкта в алфавите AC ′ , а функция возвращает индекс
соответствующего конъюнкта в алфавите A.
Обозначим мощность алфавита AC ′ через n′ . Выпишем в этих обозначениях математическое ожидание, которое и будет решением первой
задачи апостериорного вывода:
′
n
2∑
−1
n′
(T⟨GInd(i,m),GInd(2
−1−i,m)⟩
× Pc )[0](I × Pac )[i].
i=0
Соответственно, если все детерминированные свидетельства возможны, то решением второй задачи апостериорного вывода для стохастического свидетельства будет:
′
P⟨(C
c
′
,Pac )⟩
=
n
2∑
−1
i=0
n′
T⟨GInd(i,m),GInd(2 −1−i,m)⟩ × Pc
(I × Pac )[i].
n′ −1−i,m)⟩
⟨GInd(i,m),GInd(2
(T
× Pc )[0]
Если какое-либо детерминированное свидетельство невозможно и
при этом оценки, задаваемые стохастическим свидетельством для данного детерминированного, нулю не равны, то мы говорим, что такое
свидетельство невероятное.
Теперь рассмотрим ФЗ с интервальными оценками вероятности и
стохастическое свидетельство. Для решения первой задачи апостериорного вывода нам нужно найти максимум и минимум функции:
′
n
2∑
−1
n′
(T⟨GInd(i,m),GInd(2
−1−i,m)⟩
i=0
29
× Pc )[0] (I × Pac )[i].
Так как функция – линейная, то нам необходимо решить две соответствующие задачи ЛП.
Для второй задачи апостериорного вывода функция перестает быть
линейной. Из-за этого мы не сможем точно найти соответствующие максимумы и минимумы, не выходя за рамки задач линейного программирования. Будем строить не точное решение, а накрывающее его. Для
этого вычислим:
(
)
′
⟨GInd(i,m),GInd(2n −1−i,m)⟩
′
T
× Pc
n
Pc ⟨GInd(i,m),GInd(2 −1−i,m)⟩,min = min
′
n
(T⟨GInd(i,m),GInd(2 −1−i,m)⟩ × Pc )[0]
и
(
Pc ⟨GInd(i,m),GInd(2
n′
−1−i,m)⟩,max
= max
n′
T⟨GInd(i,m),GInd(2 −1−i,m)⟩ × Pc
′
(T⟨GInd(i,m),GInd(2n −1−i,m)⟩ × Pc )[0]
)
.
Будем считать решением второй задачи апостериорного вывода в
случае стохастического свидетельства и интервальных оценок оценки:
′
n
2∑
−1
Pc ⟨GInd(i,m),GInd(2
n′
−1−i,m)⟩,min
(I × Pac )[i]
i=0
и
′
n
2∑
−1
Pc ⟨GInd(i,m),GInd(2
n′
−1−i,m)⟩,max
(I × Pac )[i].
i=0
Неточные свидетельства. Рассмотрим последний вид свидетельств –
неточные.
Неточное свидетельство представляет собой фрагмент знаний с инa,+
тервальными оценками (C ′ , Pa,−
c , Pc ). Будем трактовать его следуюa,+
щим образом [3]: неточное свидетельство (C ′ , Pa,−
c , Pc ), это семейство
всевозможных стохастических свидетельств (C ′ , Pac ), таких чт Pa,−
≤
c
Pac ≤ Pa,+
c .
В данном случае мы сталкиваемся с выходом из задач ЛП уже на
этапе решения первой задачи апостериорного вывода. Приблизим ре30
шение, зафиксировав максимумы и минимумы значений оценок для
каждого детерминированного. Получим две линейные оценки, которые
накроют истинные интервальные оценки для решения первой задачи
апостериорного вывода:
′
n
2∑
−1
min
′
(T
⟨GInd(i,m),GInd(2n −1−i,m)⟩
× Pc )[0](I × Pac )[i] ,
i=0
′
n
2∑
−1
max
(T
′
⟨GInd(i,m),GInd(2n −1−i,m)⟩
× Pc )[0](I × Pac )[i] .
i=0
В случае, когда исходный ФЗ имеет скалярные оценки, эти формулы
точные, а не накрывающие.
Для решения второй задачи апостериорного выввода достаточно
найти:
′
n
2∑
−1
n′
min
Pc ⟨GInd(i,m),GInd(2 −1−i,m)⟩,min (I × Pac )[i] ,
i=0
′
n
2∑
−1
max
Pc
′
⟨GInd(i,m),GInd(2n −1−i,m)⟩,max
(I × Pac )[i] .
i=0
Поддержание непротиворечивости и апостериорный вывод в
ФЗ над идеалом дизъюнктов. Запишем пример вектора вероятностей элементов идеала дизъюнктов фрагмента знаний, построенного
над алфавитом мощности 2 из атомов x1 , x2 , и вектор, получающийся
при вычитании его из единичного вектора.
0
1
p(x1 )
p(x1 )
Pd =
p(x ) , 1 − Pd = p(x ) .
2
2
p(x1 ∨ x2 )
p(x1 x2 )
Рассмотрим соотношение для перехода от вектора оценок вероятностей дизъюнктов к вектору оценок вероятностей квантов En In (1−Pd ) =
31
0 ··· 1
Pq , где En = · · · 1 · · · – матрица, в которой на всех позициях
1 ··· 0
кроме второй диагонали стоят нули, а вторая диагональ занята единицами. Равенство становится очевидным при раскрытии левой части
уравнения.
Домножим обе части уравнения на матрицу Jn , получим: Jn En In (1−
Pd ) = Jn Pq = Pc . Введем новую матрицу Kn :
(
)[n] (
)[n] (
)[n]
0 1
1 −1
1 1
=
Kn = Jn En In =
0 1
1 0
0 1
((
)(
)(
))[n]
1 1
0 1
1 −1
=
0 1
1 0
0 1
(
)[n]
1 0
, K1 = K.
1 −1
Используя новое обозначение мы можем записать выражение вектора вероятностей идеала конъюнктов через вектор вероятности идеала
дизъюнктов: Kn (1 − Pd ) = Pc . Также заметим, что K−1
n = Kn . Введем
′
обозначение: Pd = 1 − Pd . Перепишем ранее полученные уравнения
используя введенное обозначение:
′
Pc = Kn Pd .
Рассмотрим уравнения апостериорного вывода для ФЗ над идеалом
дизъюнктов, используя полученные ранее формулы для идеала конъюнктов.
Следующие теоремы были сформулированы в соавторстве с А.А. Золотиным. Математическая постановка – А.А. Золотин, формальное доказательство – Е.А. Мальчевская.
Теорема 2.4 [1]
′
p(⟨ci , cj ⟩) = (d⟨i,j⟩ , Pd ),
⟨i,j⟩
~
где d⟨i,j⟩ = ⊗k=n−1
dk ,
k=0
32
+
d , если xk входит в ci ;
⟨i,j⟩
~
dk =
d− , если xk входит в cj ;
do , иначе.
(
)
( )
( )
1
0
1
′
причем d+ =
, d− =
, do =
и Pd = 1 − Pd .
−1
1
0
Доказательство. Выполним ряд преобразований. Вероятность свидетельства, поступившего в ФЗ над идеалом конъюнктов равна p(⟨i, j⟩) =
(r⟨i,j⟩ , Pc ) [22]. Подставим вместо Pc полученное ранее выражение для
вектора идеала дизъюнктов:
′
′
⟨i,j⟩
p(⟨i, j⟩) = (r⟨i,j⟩ , Pc ) = (r⟨i,j⟩ , Kn Pd ) = (KT
, Pd ),
nr
(
)[n]
1 1
⟨i,j⟩
~
KT
, r⟨i,j⟩ = ⊗k=n−1
rk ,
n =
k=0
0 −1
+
r , если xk входит в ci ;
⟨i,j⟩
~
rk =
r− , если xk входит в cj ;
ro , иначе.
(
)
( )
( )
1
0
1
, r+ =
, r− =
, ro =
.
−1
1
0
⟨i,j⟩
′
′
⟨i,j⟩
′
⟨i,j⟩
~
rk ), Pd ).
(KT
, Pd ) = ((KT )[n] (⊗k=n−1
rk ), Pd ) = (⊗k=n−1
(KT~
nr
k=0
k=0
⟨i,j⟩
Заметим, что вектор ~
rk может принимать только три значения, а
матрица KT
n – одно, следовательно будет существовать только 3 воз⟨i,j⟩
⟨i,j⟩
можных означивания вектора ~
dk = KT~
rk . Рассмотрим их:
(
)( ) (
)
1 1
0
1
d+ = KT r+ =
=
,
0 −1
1
−1
(
)(
) ( )
1 1
1
0
d− = KT r− =
=
,
0 −1
−1
1
(
)( ) ( )
1 1
1
1
do = KT ro =
=
.
0 −1
0
0
⟨i,j⟩
~
Тогда, зная, что d⟨i,j⟩ = ⊗k=n−1
dk
k=0
■
33
′
получаем, что p(⟨ci , cj ⟩) = (d⟨i,j⟩ , Pd ).
Теорема 2.5 [1]
′
′
,⟨i,j⟩
Pd = (d⟨i,j⟩1 ,P′ ) M⟨i,j⟩ × Pd ,
где M
~ ⟨i,j⟩
M
k
d
k=n−1 ~ ⟨i,j⟩
Mk ,
=
⊗
k=0
+
M , если xk входит
M− , если xk входит
o
⟨i,j⟩
=
(
причем M+ =
в ci ;
в cj ;
M , иначе.
(
(
)
)
)
1 −1
0 1
1 0
′
, M− =
, Mo =
и Pd =
0 0
0 1
0 1
1 − Pd .
Доказательство.
Решение второй задачи апостериорного вывода для ФЗ над идеалом
⟨i,j⟩
конъюнктов записывается как Pc = (d⟨i,j⟩1 ,P′ ) T⟨i,j⟩ × Pc . Заметим, что
d
Pc ⟨i,j⟩ = Kn (1 − Pd ⟨i,j⟩ ). Подставим вместо Pc и Pc ⟨i,j⟩ полученные ранее
выражения для векторов идеалов дизъюнктов, а знаменатель заменим
на выражение из предыдущей теоремы:
P⟨i,j⟩
=
c
Kn (1 − Pd ⟨i,j⟩ ) =
′
Pd ,⟨i,j⟩ ) =
1
(r⟨i,j⟩ , Pc )
T⟨i,j⟩ × Pc
1
T⟨i,j⟩ × Kn × (1 − Pd )
′
⟨i,j⟩
(d , Pd )
1
⟨i,j⟩
K−1
× Kn × (1 − Pd )
′
n ×T
⟨i,j⟩
(d , Pd )
Подробнее распишем произведение матриц и воспользуемся тем, что
K−1
n = Kn :
⟨i,j⟩
K−1
× Kn = Kn × T⟨i,j⟩ × Kn = (K)[n] × T⟨i,j⟩ × (K)[n]
n ×T
⟨i,j⟩
⟨i,j⟩
~ ,
T
Ранее было
= ⊗k=n−1
k=0
k
получено [23], что T
+
T , если xk входит в ci ;
⟨i,j⟩
~
T
=
T− , если xk входит в cj ;
k
To , иначе.
(
)
(
)
(
)
0
1
1
−1
1
0
причем T+ =
, T− =
, To =
.
0 1
0 0
0 1
~ ⟨i,j⟩ , как было показано, может принимать 3 знаТак как матрица T
k
34
~ ⟨i,j⟩ = K × T
~ ⟨i,j⟩ × Kn есть
чения, а матрица K – одно, то у матрицы M
k
k
3 варианта означивания:
(
)(
)(
) (
)
1 0
0 1
1 0
1 −1
M+ = KT+ K =
=
,
1 −1
0 1
1 −1
0 0
(
)(
)(
) (
)
1 0
1 −1
1 0
0 1
M− = KT− K =
=
,
1 −1
0 0
1 −1
0 1
)(
)(
) (
)
(
1
0
1
0
1
0
1
0
=
.
Mo = KTo K =
1 −1
0 1
1 −1
0 1
′
,⟨i,j⟩
Получим, что Pd
=
1
′
(d⟨i,j⟩ ,Pd )
′
M⟨i,j⟩ × Pd ,
k=n−1 ~ ⟨i,j⟩
и M⟨i,j⟩ =
⊗
k=0 Mk ,
+
M , если xk входит в ci ;
~ ⟨i,j⟩ =
M
M− , если xk входит в cj ;
k
Mo , иначе.
(
)
(
)
(
)
1
−1
0
1
1
0
причем M+ =
, M− =
, Mo =
.
0 0
0 1
0 1
■
2.4. Существующие программные реализации
В качестве основы использовалась библиотека AlgBN KPB Reconciler
cpp.v.01 [21], упомянутая ранее и написанная в 2011 году на C++. Фрагмент знаний в случае данной библиотеки представляется одним классом со всей информацией, такой как вероятностные оценки и размер
фрагмента знаний, хранимой в полях. Методы, отвечающие за формирование ФЗ, такие как конструкторы, и методы, отвечающие за локальный априорный вывод и апостериорный вывод, также хранятся в этом
классе. Такой клиент называется «толстым», потому что реализация
различных функциональностей не разделена по разным классам, а находится в одном, объемном классе. Преимущество данного подхода в
том, что всевозможные виды ФЗ, такие как интервальные, скалярные
и бинарные, мы можем представить с помощью единой структуры, то
есть унифицировать работу со всеми видами фрагментов знаний.
Также была взята за основу библиотека AlgBN Modeler j.v.01 [19],
35
которая была написана в 2009 году. Основной её особенностью и обоснованием того, что клиент – «тонкий», является то, что в ней разные
функциональности разнесены в разные структуры классов, таким образом каждая подструктура библиотеки отвечает за свою задачу.
Однако для интеграции со структурной частью объемлющего проекта было решено переработать существующие решения на языке C#. В
данной библиотеке основной упор сделан на структуру интерфейсов. В
работе рассматриваются 3 вида фрагментов знаний: интервальный, скалярный и бинарный. В частности, было замечено, что бинарный фрагмент может быть задан, как скалярный, а скалярный, соответственно,
как интервальный. Из данного наблюдения получилось сразу две цепи
наследования. Первая цепь это наследование getter’ов, методов, которые считывают вероятностные оценки фрагментов знаний. Бинарный
ФЗ может быть считан, как скалярный, а скалярный как интервальный.
На Рис. 8, который был заимствован из [9], показано, как происходит
наследование.
Вторая цепь наследования это наследование setter’ов, методов, которые задают вероятностные оценки фрагментов знаний. Бинарный ФЗ
может быть задан как скалярный, а скалярный как интервальный. На
Рис. 8 показано, как в данном случае происходит наследование.
Вышеупомянутые знания были применены и к фрагментам знаний,
которые формально представляются, как идеал конъюнктов, дизъюнктов или квантов. В следствии чего были получены взаимосвязи, которые можно видеть на Рис. 8. Также упомянутые зависимости были
использованы и в структурах пропагаторов и инфереров, то есть машин
осуществляющих апостериорный и априорный вывод соответственно.
В программном комплексе использовалась библиотека для решения
задач линейного программирования lp_solve55, которая позволяет задавать целевую функцию, ограничения на переменные, максимизировать или минимизировать целевую функцию.
36
Рис. 8. Иерархия интерфейсов [19].
37
2.5. Выводы по главе
В данной главе описаны как классическая модель фрагмента знаний, так и альтернативные, связанные с этими моделями определения.
Рассмотрены математические аппараты для осуществления локального
логико-вероятностного вывода: априорного и апостериорного. Доказаны две теоремы, в которых формализуется апостериорный вывод в ФЗ,
построенных над идеалом дизъюнктов. Описаны существующие программные реализации, которые были взяты за основу, а также упомянута библиотека, которая использовалась в разработанном программном комплексе.
38
3. Архитектура разработанного программного комплекса
3.1. Введение
В предыдущей главе была рассмотрена теоретическая основа работы, в этой главе рассмотрим некоторые аспекты программной реализации. В начале опишем структуру ABN, состоящую из интерфейсов
и классов, которые ответственны за хранение и создание фрагментов
знаний с интервальными, скалярными и бинарными оценками вероятности. Приведем срез структуры, связанный с интервальными ФЗ, для
бинарных и скалярных ФЗ набор и функциональность классов и интерфейсов похожая. Разберем структуру Inferrer, отвечающую за поддержание и проверку непротиворечивости и за априорный вывод. Приведена только та часть структуры, которая работает со скалярными ФЗ, в
интервальном случае набор классов и интерфейсов аналогичен. Приведем структуру Propagator, состоящую из классов, абстрактных классов
и интерфейсов, отвечающую за апостериорный логико-вероятностный
вывод, а точнее за пропагацию детерминированного, стохастического
или неточного свидетельства во ФЗ со скалярными или интервальными оценками вероятности. А также опишем вспомогательные классы.
3.2. Особенности наследования компонентов в системе
Архитектура данной работы воспроизводит архитектуру библиотеки AlgBN Modeler j.v.01 [19]. На Рис. 9 изображена диаграмма связи
всех интерфейсов, которые используются в структуре данной библиотеки, отвечающей за создание и хранение ФЗ (ABN).
Также была прослежена зависимость между абстрактными классами, которая изображена на Рис. 10.
Мнемонику абстрактного класса KnowledgePatternBasis [19] было
решено изменить на KPSupp (сокращенно от Knowledge Pattern Support),
39
Рис. 9. Диаграмма интерфейсов.
так как это существенно.
И далее были реализованы такие классы, как IntervalDisjKP, IntervalConjKP, IntervalQuantKP, ScalarDisjKP, ScalarConjKP, ScalarQuantKP,
BinaryDisjKP, BinaryConjKP, BinaryQuantKP, связь между которыми
изображена на Рис. 11. В некоторых местах код был упрощен по причине особенности платформы, на которой была написана программная
часть, но это все же требует дополнительных исследований.
Особенности наследования интерфейсов и классов, отвечающих за
хранение фрагментов знаний, использованы и в принципах наследования в других структурах программного комплекса, отвечающих за
априорный и апостериорный логико-вероятностный вывод, которые мы
40
Рис. 10. Диаграмма зависимости абстрактных классов.
Рис. 11. Диаграмма классов.
разберем далее.
41
3.3. Структура создания и хранения ФЗ ABN
На Рис. 12 приведена диаграмма интерфейсов структуры ABN, которая отвечает за интервальный фрагмент знаний.
Evidence и LocalEvidence позволяют всем классам, наследующих у
них, считывать глобальный индекс ФЗ.
KPSupp_I содержит в себе методы, которые считывают мощность
алфавита, на котором построен рассматриваемый ФЗ, и количество в
нем элементов.
ConjKP_I, DisjKP_I, QuantKP_I показывают принадлежность рассматриваемого ФЗ к какому-либо классу представления ФЗ: конъюнктов, дизъюнктов или квантов соответственно.
IntervalGetter и IntervalSetter содержат методы, которые считывают
вероятностные оценки ФЗ и задают их соответственно.
И IntervalConjKP_I, IntervalDisjKP_I, IntervalQuantKP_I обозначают методы, присущие интервальным конъюнктному, дизъюнктному
и квантовому ФЗ соответственно.
Структуры LinearForm и Extention позволяют для каждого ФЗ задавать список пропозициональных формул, для которых в последствии
будет выполняться априорный вывод. Пропозициональная формула задается вектором из коэффициентов в разложении формулы в СНДФ по
конъюнктам исходного ФЗ.
На Рис. 13 показана взаимосвязь классов IntervalConjKP, IntervalDisjKP, IntervalQuantKP, которые реализуют методы тех интерфейсов,
которые были рассмотрены ранее и также наследуют часть реализованных методов абстрактного класса IntervalKP.
42
Рис. 12. Диаграмма интерфейсов.
3.4. Структуры локального-логико-вероятностного вывода и вспомогательные структуры
3.4.1. Структура Inferrer априорного логико-вероятностного вывода
Интерфейс InferrerI содержит методы, которые выдают сведения о
совместимости оценок и проверяют совместимы ли оценки ФЗ и улучшились они. Оценки могут улучшиться только у ФЗ с интервальными
оценками. То есть реализующий класс для данного инетрфейса должен
обрабатывать ФЗ, проверять, противоречив ли ФЗ или нет и проверять,
стали ли оценки более точными.
С помощью методов интерфейса LocalInferrerI можно проверить непротиворечивость ФЗ и получить копию ФЗ, заданного на входе, с переобозначенными оценками, если оценки уточнились.
Метод интерфейса ScalarLocalInferrerI либо возвращает ФЗ, постро43
Рис. 13. Диаграмма классов, относящихся к интервальному ФЗ.
енный над квантами, соответствующий исходному ФЗ, либо сообщает
о том, что исходный ФЗ противоречив.
Класс ScalarConjunctsLocalInferrer реализует методы всех вышеупомянутых интерфесов, а также содержит средства, в частности метод
processKP(), для проведения априорного вывода, т.е. подсчета вероятности пропозициональной формулы на основе оценок вероятности исходного ФЗ, которые используют структуры LinearForm и Extention из
более обширной структуры ABN, рассмотренной ранее. Метод processKP
позволяет для каждой пропозициональной формулы из списка, содержащемся в исходном ФЗ, посчитать результат априорного вывода.
На Рис. 14 изображены взаимосвязи классов и интерфейсов, которые были описаны.
44
Рис. 14. Диаграмма структуры инфереров.
3.4.2. Структура Propagator апостериорного логико-вероятностного вывода
Структура Propagator, состоящая из классов, абстрактных классов
и интерфейсов, отвечает за апостериорный логико-вероятностный вывод, а точнее за пропагацию детерминированного, стохастического или
неточного свидетельства во ФЗ со скалярными или интервальными
оценками вероятности. Далее приведен только срез структуры, соответствующий пропагации детерминированного свидетельства во ФЗ со
скалярными оценками вероятности, для остальных случаев структуры
аналогичные.
Интерфейс PropagatorI содержит один метод, которые позволяет
узнать, какая ошибка произошла при работе программы.
Единственный метод интерфейса ScalarPropagatorI возвращает оценку свидетельства, пропагируемого во ФЗ. Оценка, полученная после
пропагации свидетельства является решением первой задачи апостериорного логико-вероятностного вывода.
С помощью методов интерфейса LocalPropagatorI можно установить
ФЗ, в котором будет производиться пропагация, выполнить пропагацию
и получить пересчитанный ФЗ после пропагации.
Абстрактный класс ScalarConjunctsLocalPropagator наследует методы ранее описанных интерфейсов, а также задает новые методы, которые позволяют проверить ФЗ и свидетельство на «адекватность».
Например обязательное правило для свидетельства то, что идеал конъ45
юнктов, на котором оно построено, должно быть подмножеством идеала конъюнктов ФЗ, в который оно пропагируется. Если это условие не
выполняется, то пропагация произойти не может.
Интерфейс DeterministicScalarConjunctsLocalPropagatorI представляет из себя обобщенный интерфейс, который наследует методы ранее
приведенных интерфейсов.
Класс DeterministicScalarConjunctsLocalPropagator наследует от рассмотренного абстрактного класса ScalarConjunctsLocalPropagator и от
интерфейса DeterministicScalarConjunctsLocalPropagator и определяет
методы, которые ранее не были определены.
Рис. 15. Диаграмма структуры пропагаторов.
На Рис. 15 изображены взаимосвязи той структуры Propagator.
3.4.3. Вспомогательные структуры
В этом разделе приведем классы, используемые в основных структурах ABN, Inferrer и Propagator.
Класс LP является классом-фасадом для импортируемой библиотеки lp_solve55, предназначенной для решения задач линейного программирования (ЛП). Этот класс унифицирует процесс решения задач ЛП,
используемых при пропагации свидетельств, класс - прослойка, позволяющий задавать количество переменных, используемых в задаче ЛП,
46
коэффициенты у переменных в целевой функции и в ограничениях.
Также имеется возможность решить задачу ЛП, как по максимизации
целевой функции, так и по минимизации. В результате решения задачи
мы получаем либо оптимальные значения рассматриваемых переменных, либо информацию о том, что задача не имеет решения. Также имеется возможность получения более подробной информации о возникшей
проблеме. Все эти функции поддерживаются используемой библиотекой (lp_solve55) и к большинству из них был налажен доступ через
вспомагательный класс LP.
Структура Alphabet позволяет работать с алфавитом, например с
глобальными и локальными индексами атомов, находить строковое представление атома по его глобальному индексу. В структуре Exceptions
содержатся классы, которые задают новые виды исключений. Пространство Collectors содержит классы, которые упрощают подсчет математического ожидания в пропагаторах. Структура MatrixTransform определяет множество операций с матрицами In и Jn . Класс Utils является
вспомогательным. С помощью его методов можно, например сравнить
на равенство два вещественных числа.
Вынесение некоторых функций и свойств в отдельные вспомогательные классы эффективно благодаря тому, что происходит «разделение ответственности» и в случае, если нам будет необходимо заменить
какую-либо функцию, то мы сможем заменить ее всего лишь в одном
месте.
3.5. Выводы по главе
В данной главе разобраны принципы наследования классов и интерфейсов в разработанной в рамках проекта системе. Рассмотрены структуры разработанного комплекса программ, реализующие создание ФЗ
и осуществление локального логико-вероятностного вывода, а также те
части комплекса, которые являются вспомогательными, для ранее упомянутых.
47
4. Программная реализация
4.1. Введение
Ранее были описаны структуры и их взаимосвязь в комплексе программ. В данной главе приведен основной спектр функциональности
разработанного комплекса. Описаны примеры работы и некоторые математические выкладки для рассматриваемых примеров. Также в некоторых случаях приведены выдержки из исходного кода, которые реализуют соответствующую функциональность.
4.2. Примеры работы программного комплекса. Проверка и поддержание непротиворечивости
Рассмотрим пример проверки непротиворечивости и ее поддержание во фрагментах знаний. Поддержать непротиворечивость, то есть
сузить оценки до непротиворечивых, можно только в интервальном ФЗ,
в скалярном же мы можем только проверить, являются ли оценки согласованными или нет.
Пример проверки непротиворечивости в скалярном ФЗ.
вход поступает ФЗ (C, Pc ) со скалярными оценками вероятности
На
1
0.7
Pc =
0.5 .
0.3
В результате проверки непротиворечивости программа сообщает о
непротиворечивости заданного ФЗ.
На листинге 1 приведен исходный код, который позволяет создать
ФЗ scKP со скалярными оценками вероятности, построенный над идеалом конъюнктов, создать соответствующую ему машину для априорного вывода inf_sc и с помощью метода processKP() провести проверку
48
непротиворечивости . Узнать, согласован данный ФЗ или нет можно
узнать с помощью метода isConsistent().
ScalarConjKP_I scKP = new ScalarConjKP (
Convert . ToInt64 (”11”, 2) ,
new [] {1, 0.7 , 0.5, 0.3}) ;
var inf_sc = new ScalarConjunctsLocalInferrer ();
inf_sc . processKP (scKP);
inf_sc . isConsistent ();
Листинг 1. Проверка непротиворечивости в скалярном ФЗ
Пример проверки непротиворечивости в интевальном ФЗ. Фраг+
мент знаний (C, P−
c , Pc ) с интервальными оценками вероятности.
P−
=
c
и
1
0.46
0.29
0.33
1
0.7
.
P+
c =
0.5
0.9
В результате программа выдаст суженные оценки вероятности:
1
0.46
P−
=
c
0.33
0.33
и
P+
=
c
1
0.7
0.5
0.5
49
.
а также сообщит о том, что оценки вероятности заданного ФЗ согласованы.
На листинге 2 приведен исходный код, который позволяет создать
ФЗ intKP с интервальными оценками вероятности, построенный над
идеалом конъюнктов, создать соответствующую ему машину для априорного вывода inf и с помощью метода processKP() провести проверку
непротиворечивости . Узнать, согласован данный ФЗ или нет можно
узнать с помощью метода isConsistent(). В дальнейшем не будем останавливаться на создании ФЗ подробно.
IntervalConjKP_I intKP = new IntervalConjKP (
Convert . ToInt64 (”11”, 2) ,
new [] {1, 0.46 , 0.29 , 0.33} ,
new [] {1, 0.7 , 0.5, 0.9}) ;
Console . WriteLine ( intKP . ToString ());
var inf = new IntervalConjunctsLocalInferrer ();
inf. processKP ( intKP);
inf. isConsistent ();
Листинг 2. Проверка непротиворечивости в интервальном ФЗ
4.3. Примеры работы программного комплекса. Априорный вывод
Пример априорного вывода во ФЗ со скалярными оценками.
На вход подается ФЗ (C, Pc ), заданный над алфавитом мощности 2,
т.е. состоящий из двух атомов A = {x1 , x2 }, со скалярными оценками
вероятности:
1
0.7
Pc =
0.5 .
0.3
Также мы хотим посчитать вероятность пропозициональной формулы x1 =⇒ x2 на основе оценок вероятностей данного ФЗ и вектора
коэффициентов, которые соответствуют коэффициентам в разложении
данной пропозициональной формулы в СДНФ по конъюнктам из ФЗ:
50
Pac =
1
−1
0
1
.
Вычисляется вероятность пропозициональной формулы: p(x1 =⇒
x2 ) = 0.6. Также есть возможность узнать, можно ли сузить данные
оценки вероятности и совместны ли они. Программа сообщает, что
оценки совместные, но сузить их нельзя. Это следует из того, что оценки точечные.
На листинге 3 с помощью метода addLinearForm() задается пропозициональная формула для уже существующего скалярного ФЗ, создание
которого описано на листинге 1. С помощью метода inf_sc.processKP()
проводится априорный вывод и считается нижняя и верхняя оценка вероятность поступившей формулы. В данном случае границы совпадут.
scKP. addLinearForm (” Implication ”, 1, −1, 0, 1);
inf_sc . processKP (scKP);
inf_sc . getResult (). getLinearForm (” Implication ”). getLB ();
inf_sc . getResult (). getLinearForm (” Implication ”). getUB ();
Листинг 3. Априорный вывод в ФЗ со скалярными оценками
Пример априорного вывода во ФЗ с интервальными оценками.
+
На вход подается ФЗ (C, P−
c , Pc ), заданный над алфавитом мощности 2,
т.е. состоящий из двух атомов A = {x1 , x2 }, с интервальными оценками
вероятности:
1
0.46
P−
c =
0.29
0.33
51
и
P+
=
c
1
0.7
0.5
0.9
.
Посчитаем вероятность пропозициональной ф-лы x1 ≡ x2 на основе
оценок вероятностей данного ФЗ и вектора коэффициентов, которые
соответствуют коэффициентам в разложении данной пропозициональной формулы в СДНФ:
1
−1
Pac =
−1 .
2
В результате проверки на непротиворечивость оценки уточнятся:
1
0.46
−
Pc =
0.33
0.33
и
1
0.7
+
Pc =
0.5 .
0.5
В данном случае мы получаем интервальные оценки вероятности
пропозициональной формулы: 0.46 ≤ p(x1 ≡ x2 ) ≤ 1. Программа сообщит о том, что совместные и могут быть сужены.
На листинге 4 приведен исходный код решения задачи априорного вывода для интервального ФЗ. Вычисление происходит аналогично
вычислению на листинге 3.
intKP. addLinearForm (” Equivalence ”, 1, −1, −1, 2);
inf. processKP ( intKP);
inf. getResult (). getLinearForm (” Equivalence ”). getLB ();
52
inf. getResult (). getLinearForm (” Equivalence ”). getUB ();
Листинг 4. Априорный вывод в ФЗ с интервальными оценками
4.4. Примеры работы программного комплекса. Апостериорный вывод
Рассмотрим примеры пропагации различных видов свидетельств в
интервальные или скалярные ФЗ.
Пример пропагации детерминированного свидетельства во фрагмент знаний со скалярными оценками. На вход подается ФЗ
(C, Pc ) со скалярными оценками вероятности
1
0.7
Pc =
0.5
0.3
и детерминированное свидетельство : ⟨x1 ⟩.
В результате пропагации мы получаем в качестве решения первой
задачи апостериорного вывода значение p(⟨x1 ⟩|(C, Pc )) = 0.7, а в качестве решения второй задачи апостериорного вывода вектор с оценками
вероятности:
Pc
⟨x1 ⟩
1
1
=
0.4285
0.4285
.
На листинге 5 приведен исходный код решения задач апостериорного вывода для скалярного ФЗ и детерминированного свидетельства.
Сначала создается соответствующий ФЗ kp, свидетельство evid и машина апостериорного вывода scprop, осуществляющая решение задач.
53
С помощью метода propagate() осуществляется решение задач апостериорного вывода. С помощью метода getEvidenceProbability() можно
получить решение первой задачи, а с помощью getResult() – второй.
ScalarConjKP_I kp = new ScalarConjKP (
Convert . ToInt64 (”11”, 2) ,
new [] {1, 0.7, 0.5 , 0.3}) ;
DeterministicScalarConjunctsLocalPropagatorI scprop = new
DeterministicScalarConjunctsLocalPropagator (kp);
BinaryConjKP_I evid = new BinaryConjKP (
Convert . ToInt64 (”01”, 2));
scprop . propagate (evid);
scprop . getEvidenceProbability ();
scprop . getResult (). GetPointEstimate ();
Листинг 5. Пропагация детерминированного свидетельства во фрагмент знаний
со скалярными оценками
Пример пропагации детерминированного свидетельства в ФЗ
+
с интервальными оценками. На вход подается ФЗ (C, P−
c , Pc ) с
интервальными оценками вероятности:
P−
=
c
и
1
0.2
0.3
0.06
1
0.4
P+
=
c
0.58
0.29
и детерминированное свидетельство : ⟨x1 ⟩.
В результате пропагации мы получаем в качестве решения первой
+
задачи апостериорного вывода 0.2 ≤ p(⟨x1 ⟩|(C, P−
c , Pc )) ≤ 0.4, а в качестве решения второй задачи апостериорного вывода векторы с оценками вероятности:
54
Pc ⟨x1 ⟩,−
=
1
1
0.15
0.15
и
Pc ⟨x1 ⟩,−
1
1
=
1 .
1
На листинге 6 приведен исходный код решения задач апостериорного вывода для интервального ФЗ и детерминированного свидетельства.
Вычисление и получение результата происходит аналогично листингу 5.
IntervalConjKP_I kp = new IntervalConjKP (
Convert . ToInt64 (”11”, 2) ,
new [] {1, 0.2, 0.3 , 0.06} ,
new [] {1, 0.4, 0.58 , 0.29}) ;
DeterministicIntervalConjunctsLocalPropagator prop = new
DeterministicIntervalConjunctsLocalPropagator (kp);
var evid = new BinaryConjKP (
Convert . ToInt64 (”01”, 2));
prop. propagate (evid);
prop. getEvidenceProbabilityLB ());
prop. getEvidenceProbabilityUB ());
prop. getResult (). GetBoundsL ();
prop. getResult (). GetBoundsU ();
Листинг 6. Пропагация детерминированного свидетельства в ФЗ с
интервальными оценками
Пример пропагации стохастического свидетельства во фрагмент знаний со скалярными оценками. На вход подается ФЗ
(C, Pc ) со скалярными оценками вероятности
55
Pc =
1
0.6
0.4
0.2
и стохастическое свидетельство : ⟨(C ′ , Pac )⟩, заданное над алфавитом
AC ′ = {x1 }.
(
)
1
Pac =
.
0.3
В результате пропагации мы получаем в качестве решения первой
задачи апостериорного вывода : p(⟨(C ′ , Pac )⟩|(C, Pc )) = 0.46, а в качестве решения второй задачи апостериорного вывода вектор с оценками
вероятности:
1
0.3
⟨(C ′ ,Pac )⟩
Pc
=
0.45 .
0.1
На листинге 7 приведен исходный код решения задач апостериорного вывода для скалярного ФЗ и стохастического свидетельства. Вычисление и получение результата происходит аналогично листингу 5.
ScalarConjKP_I kp = new ScalarConjKP (
Convert . ToInt64 (”11”, 2) ,
new [] {1, 0.6 , 0.4, 0.2}) ;
StochasticScalarConjunctsLocalPropagatorI scprop = new
StochasticScalarConjunctsLocalPropagator (kp);
ScalarConjKP_I evid = new ScalarConjKP (
Convert . ToInt64 (”01”, 2) ,
new [] {1, 0.3});
scprop . propagate (evid);
scprop . getEvidenceProbability ();
scprop . getResult (). GetPointEstimate ();
Листинг 7. Пропагация стохастического свидетельства во фрагмент знаний со
скалярными оценками
56
Пример пропагации стохастического свидетельства во фрагмент знаний с интервальными оценками. На вход подается ФЗ
+
(C, P−
c , Pc ) с интервальными оценками вероятности
1
0.2
−
Pc =
0.3
0.06
и
1
0.4
+
Pc =
0.58
0.29
и стохастическое свидетельство : ⟨(C ′ , Pac )⟩, заданное над алфавитом
AC ′ = {x1 }.
(
)
1
Pac =
.
0.3
В результате пропагации мы получаем в качестве решения первой
+
задачи апостериорного вывода : 0.48 ≤ p(⟨(C ′ , Pac )⟩|(C, P−
c , Pc )) ≤ 0.68,
а в качестве решения второй задачи апостериорного вывода векторы с
оценками вероятности:
1
0.3
⟨(C ′ ,Pac )⟩,−
Pc
=
0.05485
0.045
и
Pc
⟨(C ′ ,Pac )⟩,+
1
0.3
=
0.9066
0.3
.
На листинге 8 приведен исходный код решения задач апостериорно57
го вывода для интервального ФЗ и стохастического свидетельства. Вычисление и получение результата происходит аналогично листингу 5.
IntervalConjKP_I kp = new IntervalConjKP (
Convert . ToInt64 (”11”, 2) ,
new [] {1, 0.2 , 0.3, 0.06} ,
new [] {1, 0.4 , 0.58 , 0.29}) ;
StochasticIntervalConjunctsLocalPropagatorI scprop = new
StochasticIntervalConjunctsLocalPropagator (kp);
ScalarConjKP_I evid = new ScalarConjKP (
Convert . ToInt64 (”01”, 2) ,
new [] {1, 0.3});
scprop . propagate (evid);
scprop . getEvidenceProbabilityLB ();
scprop . getEvidenceProbabilityUB ();
scprop . getResult (). GetBoundsL ();
scprop . getResult (). GetBoundsU ();
Листинг 8. Пропагация стохастического свидетельства во фрагмент знаний с
интервальными оценками
Пример пропагации неточного свидетельства во фрагмент знаний со скалярными оценками. На вход подается ФЗ (C, Pc ) со
скалярными оценками вероятности
1
0.6
Pc =
0.4
0.2
a,+
и неточное свидетельство : ⟨(C ′ , Pa,−
c , Pc )⟩, заданное над алфавитом
AC ′ = {x1 }.
(
)
1
Pa,−
=
c
0.1
и
(
)
1
Pa,+
=
.
c
0.6
В результате пропагации мы получаем в качестве решения первой
58
a,+
задачи апостериорного вывода : 0.42 ≤ p(⟨(C ′ , Pa,−
c , Pc )⟩|(C, Pc )) ≤
0.52, а в качестве решения второй задачи апостериорного вывода вектор
с оценками вероятности:
1
0.1
a,+
⟨(C ′ ,Pa,−
,P
)⟩,−
c
c
Pc
=
0.4
0.0333
и
Pc
a,+
⟨(C ′ ,Pa,−
c ,Pc )⟩,+
1
0.6
=
0.48333
0.2
.
На листинге 9 приведен исходный код решения задач апостериорного вывода для скалярного ФЗ и неточного свидетельства. Вычисление
и получение результата происходит аналогично листингу 5.
ScalarConjKP_I kp = new ScalarConjKP (
Convert . ToInt64 (”11”, 2) ,
new [] {1, 0.6 , 0.4, 0.2}) ;
ImpreciseScalarConjunctsLocalPropagatorI scprop = new
ImpreciseScalarConjunctsLocalPropagator ();
scprop . setPattern (kp);
IntervalConjKP_I evid = new IntervalConjKP (
Convert . ToInt64 (”01”, 2) ,
new [] {1, 0.1} ,
new [] {1, 0.6});
scprop . propagate (evid);
scprop . getEvidenceProbabilityLB ();
scprop . getEvidenceProbabilityUB ();
scprop . getResult (). GetBoundsL ();
scprop . getResult (). GetBoundsU ();
Листинг 9. Пропагация неточного свидетельства во фрагмент знаний со
скалярными оценками
59
Пример пропагации неточного свидетельства во фрагмент зна+
ний с интервальными оценками. На вход подается ФЗ (C, P−
c , Pc )
с интервальными оценками вероятности
1
0.2
−
Pc =
0.5
0.06
и
1
0.7
+
Pc =
0.87
0.4
a,+
и неточное свидетельство : ⟨(C ′ , Pa,−
c , Pc )⟩, заданное над алфавитом
AC ′ = {x1 }.
(
)
1
Pa,−
=
c
0.2
и
(
)
1
.
Pa,+
=
c
0.73
В результате пропагации мы получаем в качестве решения первой
+
задачи апостериорного вывода : 0.227 ≤ p(⟨(C ′ , Pac )⟩|(C, P−
c , Pc )) ≤ 0.78,
а в качестве решения второй задачи апостериорного вывода векторы с
оценками вероятности:
1
0.2
′
a
Pc ⟨(C ,Pc )⟩,− =
0.12321
0.021428
60
и
Pc ⟨(C
′
,Pac )⟩,+
=
1
0.73
1
0.73
.
На листинге 10 приведен исходный код решения задач апостериорного вывода для интервального ФЗ и неточного свидетельства. Вычисление и получение результата происходит аналогично листингу 5.
IntervalConjKP_I kp = new IntervalConjKP (
Convert . ToInt64 (”11”, 2) ,
new [] {1, 0.2 , 0.5, 0.06} ,
new [] {1, 0.7 , 0.87 , 0.4}) ;
ImpreciseIntervalConjunctsLocalPropagatorI scprop = new
ImpreciseIntervalConjunctsLocalPropagator ();
scprop . setPattern (kp);
IntervalConjKP_I evid = new IntervalConjKP (
Convert . ToInt64 (”01”, 2) ,
new [] {1, 0.2} ,
new [] {1, 0.73}) ;
scprop . propagate (evid);
scprop . getEvidenceProbabilityLB ();
scprop . getEvidenceProbabilityUB ();
scprop . getResult (). GetBoundsL ();
scprop . getResult (). GetBoundsU ();
Листинг 10. Пропагация неточного свидетельства во фрагмент знаний с
интервальными оценкам
4.5. Выводы по главе
Функциональность разработанного программного комплекса покрывает базовую функциональность, необходимую для осуществления локального логико-вероятностного вывода над фрагментами знаний как
со скалярными оценками вероятности, так и с интервальными. В некоторых случаях приведен исходный код, показывающий каким образом
создается ФЗ, как для него задаются оценки и выполняются основные
61
Заключение
В ходе работы над выпускной квалификационной работой бакалавра
была достигнута основная цель – реализована библиотека на 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)
63
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, «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логиковероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой».
Полученные результаты позволяют в будущем развить функциональность данной библиотеки, реализовывать глобальный логико-веро64
ятностный вывод, а также интегрироваться с другими подпроектами,
которые связаны со структурной компонентой библиотеки.
65
Список литературы
[1] Золотин А.А., Мальчевская Е.А. Матрично-векторные алгоритмы
локального апостериорного вывода в алгебраических байесовских
сетях над идеалами дизъюнктов // Материалы международной конференции по мягким вычислениям и измерениям (в печати)
[2] Зотов М.А., Тулупьев А.Л. Вторичная структура алгебраических
байесовских сетей: статистическая оценка сложности прямого алгоритма синтеза // Международная конференция по мягким вычислениям и измерениям. 2015. Т. 2. № Секции 4–7. С. 158–162
[3] Сироткин А.В. Алгебраические байесовские сети: вычислительная
сложность алгоритмов логико-вероятностного вывода в условиях
неопределенности. — Изд-во С.-Петерб. ун-та, 2011.
[4] Сироткин А.В. Вычислительная сложность локального апостериорного вывода в алгебраических байесовских сетях// Труды СПИИРАН. 2011. Вып.3(18). С.188-214.
[5] Сироткин А.В. Локальный априорный вывод в алгебраических байесовских сетях: комплекс основных алгоритмов // Труды СПИИРАН. Вып.5. СПб.: Наука, 2007. С.100-111.
[6] Сироткин А.В. Проверка и поддержание непротиворечивости алгебраических байесовских сетей: вычислительная сложность алгоритмов // Труды СПИИРАН. 2010. Вып.4(15). С.162-192.
[7] Сироткин А.В., Тулупьев А.Л. Матричные уравнения локального
логико-вероятностного вывода в алгебраических байесовских сетях
// Труды СПИИРАН. Вып.6. СПб.: Наука, 2008. С.134-143.
[8] Тулупьев А.Л. Алгебраические байесовские сети: глобальный
логико-вероятностный вывод в деревьях смежности: Учеб. пособие.
СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 40 с. (Сер. Элементы мягких вычислений).
66
[9] Тулупьев А.Л. Алгебраические байесовские сети: логиковероятностная графическая модель баз фрагментов знаний с
неопределенностью. Санкт-Петербургский институт информатики
и автоматизации РАН”, — Изд-во С.-Петерб. ун-та, 2009.
[10] Тулупьев А.Л. Алгебраические байесовские сети: локальный
логико-вероятностный вывод: Учеб. пособие. СПб.: СПбГУ; ООО
Издательство «Анатолия», 2007. 80 с. (Сер. Элементы мягких вычислений).
[11] Тулупьев А.Л. Алгебраические байесовские сети: локальный
логико-вероятностный вывод: Учеб. пособие. СПб.: СПбГУ; ООО
Издательство «Анатолия», 2007. 80 с. (Сер. Элементы мягких вычислений).
[12] Тулупьев А.Л. Алгебраические байесовские сети: система операций глобального логико-вероятностного вывода // Информационноизмерительные и управляющие системы. 2010. №11. С. 65–72.
[13] Тулупьев А.Л. Апостериорные оценки вероятностей в алгебраических байесовских сетях // Вестн. С.-Петерб. ун-та. Сер. 10. 2012.
Вып. 2. С. 51–59.
[14] Тулупьев А.Л. Байесовские сети: логико-вероятностный вывод в
циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с. (Сер.
Элементы мягких вычислений.)
[15] Тулупьев А.Л. Вероятностная логика и вероятностные графические модели в базах фрагментов знаний с неопределенностью //
Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте. Научнопрактическая конференция студентов, аспирантов, молодых ученых
и специалистов (Коломна, 26–27 мая 2009 г.). Научные доклады. В
2-х т. Т. 1. М.: Физматлит, 2009. С. 26–46. Наука, 2006. С. 198–227.
[16] Тулупьев А.Л. Дерево смежности с идеалами конъюнктов как
67
ациклическая алгебраическая байесовская сеть // Тр. СПИИРАН.
2006. Т. 1. Вып. 3. С. 198–227.
[17] Тулупьев А.Л. Система для апостериорного вывода в алгебраических байесовских сетях и их фрагментах Algebraic Bayesian Networks
Propagator, Version 01 for Java (AlgBN Propagator j.v.01) (Свидетельство). Свид. о гос. рег. прогр. для ЭВМ. Рег. № 2009613804
(16.07.2009). Роспатент.. Бюлл. «Прогр. для ЭВМ, БД, топол. инт.
микросх.». 2009. № 4. С. 65.
[18] Тулупьев А.Л. Система для синтеза непротиворечивых алгебраических байесовских сетей и их фрагментов Algebraic BayesianNetworks
Inferrer, Version 01 for Java (AlgBN Inferrer j.v.01) (Свидетельство).
Свид. о гос. рег. прогр. для ЭВМ. Рег. № 2009613803 (16.07.2009).
Роспатент.. Бюлл. «Прогр. для ЭВМ, БД, топол. инт. микросх.».
2009. № 4. С. 65.
[19] Тулупьев А.Л. Система представления алгебраических байесовских сетей и их фрагментов Algebraic Bayesian Networks Modeler,
Version 01 for Java (AlgBN Modeler j.v.01) (Свидетельство). Свид.
о гос. рег. прогр. для ЭВМ. Рег. № 2009613802 (16.07.2009). Роспатент.. Бюлл. «Прогр. для ЭВМ, БД, топол. инт. микросх.». 2009. №
4. С. 64–65.
[20] Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети:
логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
[21] Тулупьев А.Л., Сироткин А.В. Программа для моделирования
фрагмента знаний алгебраической байесовской сети, поддержания его непротиворечивости и апостериорного вывода в нем
Algebraic Bayesian Network Knowledge Pattern Modeler, Reconciler
and Propagator Version 01 for C++ (AlgBN KP MRP cpp.v.01) (Свидетельство). Свид. о гос. регистрации программы для ЭВМ. Рег. №
2010615242(13.08.2010).Роспатент.
68
[22] Тулупьев А.Л., Сироткин А.В., Золотин А.А. Матричные уравнения нормирующих множителей в локальном апостериорном выводе
оценок истинности в алгебраических байесовских сетях // Вестник
СПбГУ. Сер. 1. Т. 2 (60). 2015. Вып. 3. С. 379–386.
[23] Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети
доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009. 400 с.
[24] Фильченков А.А., Тулупьев А.Л. Связность и ацикличность первичной структуры алгебраической байесовской сети // Вестник
СПбГУ. Сер. 1. 2013. С. 110–119.
69
Отзывы:
Авторизуйтесь, чтобы оставить отзыв