Алгебраические байесовские сети: вычислительная сложность алгоритмов логико-вероятностного вывода в условиях неопределённости

• Автор: Сироткин, Александр Владимирович
• Шифр специальности: 05.13.18, 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Санкт-Петербург
• Количество страниц: 218 с. : ил.

Оглавление
Введение

1 Вероятностные графические модели

1.1 Введение

1.2 Моделирование данных и знаний с неопределнностью .

1.3 Вероятностная логика

1.4 Сетевые структуры над случайными элементами

1.5 Выводы по главе .

2 Основные объекты и результаты теории алгебраических байесовских сетей

2.1 Введение

2.2 Вазовые объекты и индексация

2.3 Оценки вероятностей над пропозициями
2.4 Фрагмент знаний АБС.
2.5 Непротиворечивость фрагмента знаний.
2.6 Локальный априорный вывод.
2.7 Локальный апостериорный вывод и свидетельства
2.8 Апостериорный вывод над интервальными оценками . .
2.9 Недетерминированные свидетельства .
2. Алгебраические байесовские сети и вторичная структура
2. Степени непротиворечивости АБС
2. Выводы по главе .
3 Алгоритмы логиковероятностного вывода в алгебраических байесовских сетях
3.1 Введение
3.2 Формализация алгоритмов локального вывода и их
сложность .
3.3 Вероятностная семантика байесовских сетей доверия . .
3.4 Синтез АБС на основе БСД.
3.5 Устойчивость и чувствительность локального синтеза
согласованных оценок истинности
3.6 Объемлющая непротиворечивость
3.7 Выводы по главе .
4 Комплекс программ и его применение
4.1 Введение.
4.2 Среда разработки и компоненты комплекса
4.3 Реализация фрагмента знаний .
4.4 Реализация АВС.
4.5 Реализация расширенной функциональности
4.6 Примеры использования
4.7 Выводы по главе .
Заключение
А Копии документов о регистрации программ для ЭВМ
Введение
Актуальность


Одним из важных направлений исследований в области информатики является создание и изучение свойств моделей представления данных, сведений, знаний с неопределённостыо. При этом важна как выразительная часть, то есть какие варианты данных и знаний и в каких областях могут быть представлены с помощью модели, так и возможность использования этой модели в комплексах программ. А. Л. Суть первой проблемы: как в формальных системах представить и систематически обрабатывать неопределённость (недоопреде-лённость) наших знаний, с которой зачастую приходится сталкиваться на практике. В []’ отмечается, что тривиальные решения, которые сводятся просто к тому, чтобы отбросить знания (или данные) с неполнотой, непригодны по двум причинам: во-первых, отнюдь не во всех предметных областях за разумное время можно получить «полные знания», во-вторых, человек способен действовать и в условиях неполноты знаний о складывающейся ситуации. Вторая проблема заключается в отсутствии или неполноте знаний. Это может быть связано с тем, что не существует человека-эксперта, способного предоставить такие знания. Кроме того, не все эксперты готовы делиться своим знанием. Наконец, при попытках организовать машинное обучение (machine learning) по данным из баз данных нередко обнаруживается, что эти данные неполны и/или частично недостоверны (это может быть связано со способом получения данных, несовершенством приборов измерения и/или ошибок телеметрии). Борьбе с пропущенными данными посвящена, например, работа [1]. Существуют различные источники неопределённое™. В диссертационной работе мы будем ориентироваться на второй тип неопределённости. Зачастую разница между вторым и третьим классами не видна, однако она существует. Во втором классе мера неопределённости того или иного события — это вероятность наступления такого события, тогда как в третьем случае это может быть не обязательно вероятностная, хотя и, скорее всего, близкая ей по природе мера. Примерами систем с третьим типом неопределённости являются теория Демпстера-Шеффера [6,4,8], меры необходимости и возможности [,5,6; 4]. Кроме того, к третьему классу следует отнести системы HYCIN [2,2,5] и INFERNO [6]. Эти системы изначально эвристические по своей природе, однако для их описания можно предложить модель в рамках теории Демпстера-Шеффера [1]. Ко второму классу также близко исчисление инци-денций [6,1. Кроме неопределённости на уровне данных, встречается и неопределённость на уровне обработки данных, например, системы с нечёткими правилами вывода [5,2], различные имитационные системы [], динамические интеллектуальные системы []. Одна из существенных проблем обработки больших объёмов данных и знаний с неопределённостью — это невозможность полностью описать «мир», в котором мы действуем. Но для 0 бинарных переменных такое описание, в общем случае, потребует задания скалярных оценок вероятностей. Поэтому возникают вопросы о том, когда описание общего «мира» можно получить (или восстановить либо явно, либо неявно) на основе небольшого набора данных и знаний. Конечно, это потребует различных дополнительных предположений. Принцип уменьшения необходимого количества данных и знаний (за счёт особенностей их структуры) для описания «мира» получил название «декомпозируемость знаний». Мы, продолжая [], будем работать внутри класса моделей, включающих три компонента: систему переменных (показателей, параметров и пр. Кроме того, совокупность переменных разбивается (декомпозируется) на небольшие, обладающие некоторой регулярной структурой наборы, в каждом из которых элементы и связи между ними можно охарактеризовать наиболее точно. Наборы могут пересекаться, они также организуются в некоторую регулярную структуру. Регулярная структура и вероятностная неопределённость нашли своё отражение в так называемых вероятностных графических моделях [1,2]. Рассмотрим этот термин более подробно. Слово «вероятностные» в данном случае обозначает, что в качестве меры неопределённости рассматривается вероятностная мера. Такой подход позволяет гарантировать корректность результатов, так как на всех этапах вычислений и работы с такой моделью мы рассматриваем именно вероятность.