Алгебраические байесовские сети: логико-вероятностная графическая модель баз фрагментов знаний с неопределенностью

• Автор: Тулупьев, Александр Львович
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 670 с. : ил. + Прил. (с. 208-418: ил.) + прил. (с.

Оглавление

Список сокращений и обозначений

Введение

Глава 1. Системы и модели знаний с неопределенностью в ИИ

1.1. Введение

1.2. Классические экспертные системы с неопределенностью.

1.3. Меры неопределенности истинности в ИИ

1.4. Вероятность как мера истинности.

1.5. Интервальные оценки вероятностей

1.6. Базы фрагментов знаний

1.7. Вероятностные графические модели в ИИ..

1.8. Выводы по главе
Глава 2. Байесовские сети доверия.
2.1. Введение.
2.2. Структура ВСД и задача обработки свидетельств
2.3. Типы связей между узлами сети и разделимость.
2.4. Вероятности и определение БСД
2.5. Правило декомпозиции.
2.6. Преобразование многосвязной БСД
2.7. Алгоритмы логиковероятностного вывода.
2.8. Выводы по главе
Глава 3. АБС логиковероятностная графическая модель
3.1. Введение.
3.2. Бинарные последовательности и вероятность истинности.
3.3. Фрагменты знаний.
3.4. Виды свидетельств
3.5. Графы смежности
3.6. Алгебраические байесовские сети
3.7. Альтернативные модели ФЗ.
3.8. Выводы по главе
Глава 4 Локальный логиковероятностный вывод
4.1. Введение.
4.2. Непротиворечивость.
4.3. Априорный вывод.
4.4. Апостериорный вывод при различных видах исходных объектов .
4.5. Экстремальные задачи в апостериорном выводе
4.6. Матричновекторные уравнения апостериорного вывода.
4.7. Непротиворечивость альтернативных моделей ФЗ.
4.8. Выводы по главе
Глава 5. Логиковероятностный вывод в ациклической АБС.
5.1. Введение.
5.2. Степени непротиворечивости.
5.3. Свойства непротиворечивых АБС
5.4. Общая схема апостериорного вывода
5.5. Постановка задачи в случае цепи ФЗ.
5.6. Распространение влияния стохастического свидетельства.
5.7. Преобразование ациклической БСД в АБС.
5.8. Выводы по главе
Глава 6. Циклы в байесовских сетях.
6.1. Введение.
6.2. Цикл ФЗ АБС
6.3. Направленный БСДцикл.
6.4. Преобразование БСДцикла в цикл ФЗ АБС.
6.5. Непротиворечивость БСДцикла
6.6. Особые случаи и обобщения
6.7. Цикл стохастических предпочтений.
6.8. Выводы по главе .
Глава 7. Комплекс программ
7.1. Введение
7.2. Среда разработки и компоненты комплекса
7.3. Представление ФЗ и АБС
7.4. Синтез непротиворечивых оценок в ФЗ и АБС.
7.5. Апостериорный вывод в ФЗ и АБС
7.6. Обработка направленного БСДцикла
7.7. Примеры использования
7.8. Выводы по главе
Заключение.
Литература


Для более:полного и математического рассмотрения пропозициональной логики, ее аксиоматизаций, вывода и алгоритмов решения задачи выполнимости можно ознакомиться с работами [,, 2,1] или любым другим учебником математической: логики. Логика рассуждеиий: о вероятностях. Байесовские сети предназначены, в частности, для того, чтобы, построив с их помощью модель знаний экспертов о предметной области, на основании поступающих в одни узлы сети свидетельств оценивать изменяющиеся вероятности других узлов. Однако, прежде чем заниматься пропагацией, т. Американские исследователи Рональд Фагин, Джозеф Хальперн и Нимрод Ме-гиддо задались целью определить логику, которая могла бы включать в себя различного рода утверждения о вероятностях. Слово «логика» здесь понимается в стандартном математическом смысле, как совокупность языка, набора аксиом и правил вывода, при помощи которых можно получать новые утверждения. Фагин, Халь-перЕ и Мегиддо получили на этом пути интересные и важные результаты, которые в некотором смысле являются логической основой рассуждений, проводимых в аппаратах байесовских сетей. В данном разделе мы кратко изложим эти результаты. Волее подробное рассмотрение представлено в ряде работ [3-5,7], и именно по этим статьям мы излагаем материал в этом и следующем параграфах. Всякое определение логики должно начаться с языка. Язык логики рассуждений о вероятностях истинности должен включать в себя линейные утверждения о вероятностях, например р(х) > 0. Начнем с набора элементарных пропозиций (или элементарных событий) Ф = {tj, 1г,введем две константы — Т и F. Под пропозициональными формулами в данном случае будем понимать замыкание Ф под действием операций Ли-' (эти операции образуют базис, т. Назовем примитивным термом выражение вида vv((p), где (р — пропозициональная формула (мы не используем напрашивающуюся букву р для обозначения вероятности по причинам, которые станут ясны в следующем разделе, — там это уже будет не совсем вероятность). Термами нашего языка будут выражения вида a,w(cpi) -4-. Базовая формула — это выражение вида t > с, где t — терм, с — целое число; например, 2w(tj) — 3w(t2) > 1 — это базовая формула. Тогда формулы языка представляют собой замыкание множества базовых формул под действием булевских операций Л и Например, (w(xi) > 0. A-'(w(xi) + 2w(x2) > 1) является формулой. Последнее утверждение в обычных алгебраических байесовсюгх сетях, вообще говоря, запрещено (для упрощения алгоритмов вывода), но утверждения такого рода будут разрешены в так называемой расширенном фрагменте знаний. Лишь для удобства; разумеется, F можно определить как 1Л-Ч, а Т — как —F. Глава 1. Пояснение. Отметим, что введенный выше язык не позволяет свободно рассуждать об условных вероятностях. Он включает в себя проапейшие утверждения, например w{xi | х2) > 0. Л х2) — ”vv(x2) > 0. Но он не может выразить более сложные утверждения, например vv(xi | х2) + w(x2 I xi) > 0. Фагин, Хальперн и Мегиддо рассматривают логику, в которой нелинейные мономы разрешены, и сводят вывод в ней к выводу в теории вещественнозамкнутых полей (real closed fields). Однако это рассмотрение лежит полностью вне пределов рассмотрения настоящей работы. Из предыдущего раздела уже ясна семантика введенных нами формул. Однако Фагин, Хальперн и Мегиддо вводят ее немного по-друтому. Их подход легче обобщается на случай, допускающий неизмеримые формулы, и на случай рассмотрения высказываний нескольких агентов, поэтому будет полезным рассмотреть его и здесь. Пусть дано вероятностное пространство (S, Х,р). Тогда мы можем дать семантику формулам языка вероятностной логики, поставив в соответствие каждой атомарной пропозиции t измеримое множество, расширив это соответствие до всех событий естественным путем, а затем вычисляя вероятности этих событий посредством р. S к присваиванием истинностных значений элементарным пропозициям из Ф, т. T(s)(t) 6 (Т, F} для всех s 6 8 и t ? Ф. Теперь можно поставить в соответствие каждой элементарной пропозиции I множество тех миров s, где она истинна: tM = {s <= S|t(s)(t) = 1Г|. В данном разделе мы ограничиваем свое рассмотрение из мер имыми вероятностными структурами, т.