Содержание к диссертации
Введение
1 Вероятностные графические модели 16
1.1 Введение 16
1.2 Моделирование данных и знаний с неопределённостью 16
1.3 Вероятностная логика 20
1.4 Сетевые структуры над случайными элементами 23
1.5 Выводы по главе 27
2 Основные объекты и результаты теории алгебраических байесовских сетей 28
2.1 Введение 28
2.2 Базовые объекты и индексация 28
2.3 Оценки вероятностей над пропозициями 31
2.4 Фрагмент знаний АБС 34
2.5 Непротиворечивость фрагмента знаний 36
2.6 Локальный априорный вывод 43
2.7 Локальный апостериорный вывод и свидетельства 45
2.8 Апостериорный вывод над интервальными оценками 54
2.9 Недетерминированные свидетельства 58
2.10 Алгебраические байесовские сети и вторичная структура 63
2.11 Степени непротиворечивости АБС 65
2.12 Выводы по главе 70
3 Алгоритмы логико-вероятностного вывода в алгебраических байесовских сетях 71
3.1 Введение
3 3.2 Формализация алгоритмов локального вывода и их сложность 71
3.3 Вероятностная семантика байесовских сетей доверия 93
3.4 Синтез ABC на основе БСД 101
3.5 Устойчивость и чувствительность локального синтеза согласованных оценок истинности 107
3.6 Объемлющая непротиворечивость 115
3.7 Выводы по главе 119
4 Комплекс программ и его применение 121
4.1 Введение 121
4.2 Среда разработки и компоненты комплекса 121
4.3 Реализация фрагмента знаний 123
4.4 Реализация ABC 132
4.5 Реализация расширенной функциональности 141
4.6 Примеры использования 147
4.7 Выводы по главе 155
Заключение
- Вероятностная логика
- Оценки вероятностей над пропозициями
- Вероятностная семантика байесовских сетей доверия
- Реализация фрагмента знаний
Введение к работе
Актуальность темы исследования. Развитие вычислительных мощностей компьютерной техники все больше расширяет границы применимости ЭВМ. Однако существуют задачи, с которыми даже современные ЭВМ справляются существенно хуже человека. К таким задачам относятся задачи распознавания (текста, речи и т. д.), задачи предсказания неизвестных данных на основе известных, а так же задачи анализа данных, особенно связанные с неопределённостью. Неопределённость может быть вызвана как недостатком знаний, так и сложностью перевода вербальных высказываний в язык логики или иной формальный язык, удобный для обработки на ЭВМ. Способность людей выявлять закономерности в небольших системах даёт существенный выигрыш по сравнению с ЭВМ, однако возможности человека существенно ограничены. Это делает анализ достаточно больших систем почти недостижимым для человека.
Существует ряд методов, которые позволяют совмещать способности человека анализировать структуры и выявлять зависимости с возможностями ЭВМ оперировать огромными объёмами данных. В частности, большинство современных автоматизированных рабочих мест в промышленности позволяют вычислять некие параметры системы на основе весьма объёмного и интенсивного потока исходных данных, а на человека-оператора возлагается принятие решений на базе небольшой совокупности соотношений этих параметров.
В контексте вышесказанного становится понятной важность исследований в области информатики, связанных с теоретическим изучением математических свойств моделей представления данных, сведений, знаний с неопределённостью, а также подходов к моделированию рассуждений в указанном контексте. Одной из таких математических моделей являются алгебраические байесовские сети (ABC), которым преимущественно посвящена диссертация.
Применение математических моделей знаний с неопределённостью наиболее востребовано в различных прогностических системах, а также в интеллектуальных системах поддержки принятия решений. Создание программных продуктов, которые можно использовать на практике, требует не только строгой формализации математического аппарата, но также разработки и последующего анализа алгоритмов, который гарантирует, что результаты работы системы соответствуют действительности. Кроме того, в силу наличия неточности, надо чётко понимать, какая «ошибка в данных» фатальна и ведёт к неверному ответу на заданный вопрос, а какая — не повлияет на главный результат. Это влечёт необходимость построения оценок устойчивости и чувствительности логико-вероятностного вывода.
Корректность и чувствительность алгоритмов логико-вероятностного вывода отвечает на вопрос, можно ли «теоретически» использовать данные алгоритмы. Но при этом они не отвечают на вопрос, насколько ограничено (и вообще возможно) применение указанных алгоритмов на практике, и в частности, — дождёмся ли мы результатов моделирования процессов рассуждений за разумное время. Для ответа на эти вопросы требуется оценить сложность алгоритмов логико-вероятностного вывода, что и составляет основную цель диссертационной работы.
Объектом диссертационного исследования выступают алгебраические байесовские сети, а предметом — алгоритмы логико-вероятностного вывода в них.
Цель исследования. Целью диссертационного исследования является оценка эффективности алгоритмов логико-вероятностного вывода в ABC. Её достижение осуществляется посредством решения следующих задач: 1) оценить вычислительную сложность алгоритмов логико-вероятностного вывода в ABC; 2) исследовать устойчивость и чувствительность алгоритмов проверки и поддержания непротиворечивости фрагмента знаний ABC; 3) исследовать возможности расширения семантики алгебраических байесовских сетей за счёт введения новой степени непротиворечивости (на-
крывающей непротиворечивости); 4) исследовать возможности моделирования байесовской сети доверия (ВСД) с помощью ABC.
Методы исследования. При формировании понятийного аппарата и в теоретической части исследования привлечены объекты и методы линейной алгебры, теории частично упорядоченных множеств, булевой алгебры, теории вероятностей, вероятностной логики, теории графов, экстремальных задач (задачи линейного и гиперболического программирования). Проектирование и разработка комплекса программ базировалась на принципах структурного и объектно-ориентированного программирования (как при выработке решений по архитектуре кода, так и при его реализации), а также на ряде технологий, связанных с языком реализации (C++). Само диссертационное исследование по подходам, использованным для решения ряда задач по построению моделей и обработке знаний с вероятностной неопределённостью, принадлежит комплексной сфере искусственного интеллекта, в которой изучаются и разрабатываются фундаментальные основы, методы, средства и алгоритмы моделирования знаний с неопределённостью и рассуждений над ними.
Научная новизна исследования. Предложен способ вычисления матрицы, соответствующей линейному оператору ненормированного локального апостериорного вывода в случае детерминированного свидетельства, на основе выражения её через фиксированные матрицы небольшой размерности. Даны оценки сложности алгоритмов локального логико-вероятностного вывода (поддержание непротиворечивости, априорный вывод, апостериорный вывод), а также алгоритмов поддержания различных степеней непротиворечивости ABC (глобальной, интернальной, экстернальной). Конструктивно доказано, что экстернальная непротиворечивость ABC не гарантирует интернальную непротиворечивость (построен соответствующий контрпример). Предложена математическая модель согласования противоречивых данных на основе понятия «накрывающая непротиворечивость». Предложен алгоритм построения ABC, семантически эквивалентной заданной ВСД, на основе представления последней в виде дерева смежности. Предложены подходы к оценке устойчивости процесса поддержания непротиворечивости ФЗ ABC. Создан комплекс программ на языке программирования C++, реализующий локальный логико-вероятностный вывод в ABC, а так же поддержание различных степеней непротиворечивости и глобальный апостериорный вывод для ABC представленной в виде дерева смежности.
В целом в диссертации завершено решение задачи алгоритмизации логико-вероятностного вывода в ABC, рассматриваемых как особые математические модели баз фрагментов знаний с неопределённостью, а также построена система оценок вычислительной сложности соответствующих алгоритмов.
Все результаты, выносимые на защиту диссертации, являются новыми.
Практическая значимость диссертационной работы состоит в том, что ее выводы, а так же материалы позволили спроектировать и реализовывать комплекс программ, поддерживающий моделирование знаний с неопределённостью и рассуждения в условиях неопределённости в рамках теории алгебраических байесовских сетей. Основная часть этого комплекса программ реализована в виде объектно-ориентированной библиотеки на C++, что позволяет использовать ее в программных продуктах с байесовской интеллектуальной компонентой.
Материалы исследования могут быть использованы для подготовки общих и специальных курсов для студентов математических и технических специальностей по логике, вероятностной логике, искусственному интеллекту и мягким вычислениям.
Апробация результатов исследования. Результаты исследования были представлены автором на следующих конференциях: 1) VIII Международная конференция по мягким вычислениям и измерениям SCM'2005; 2) X Международная конференция по мягким вычислениям и измерениям SCM'2007; 3) XII Международная конференция по мягким вычислениям и измерениям SCM'2009; 4) Научная сессии МИФИ-
2008; 5) Научная сессии МИФИ-2009; 6) Научная сессии МИФИ-2010; 7) Научная сессии МИФИ-2011; 8) Всероссийская научная конференция по нечётким системам и мягким вычислениям, Тверь, 2006; 9) Вторая Всероссийская научная конференция с международным участием Нечёткие системы и мягкие вычисления (НСМВ-2008) 10) X Санкт-Петербургская международная конференция Региональная информатика-2006(РИ-2006) 11) XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ-2008) 12) IV международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 2007; 13) V-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 28-30 мая 2009 г.; 14) VI-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 16-19 мая 2011 г.; 15) V Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России», Санкт-Петербург, 2007; 16) Научно-практическая конференция студентов, аспирантов, молодых учёных и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009), Коломна, 26-27 мая 2009 г.; 17) Научная конференция «Информационные технологии и системы», Геленджик,
29 сентября - 03 октября, 2008 г. Кроме того, результаты диссертационного исследова
ния неоднократно докладывались на Санкт-Петербургском общегородском научном
семинаре «Информатика и компьютерные технологии» в 2005-2010 гг.
Исследования по теме диссертации были поддержаны грантом Фонда содействия отечественной науке по программе «Лучшие аспиранты РАН» (2008), грантом РФФИ (09-01-00861-а — «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределённостью»), госконтрактом 02.442.11.7289 от 28.02.2006 на выполнение НИР «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логико-вероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой» в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы», а так же грантом «У.М.Н.И.К.» (2008, 2009), госконтракт № 5353 р/7771 от 16 августа 2007 г на выполнение НИОКР по теме «Разработка методов и программных средств для создания автоматизированных систем мониторинга и управления динамическими объектами» и госконтракт №6468р/8764 от 11.01.2009 на выполнение НИОКР «Разработка автоматизированных систем для нужд навигации, управления движением, медицины, а также их компонентов, включая датчики, приборы, алгоритмы и программное обеспечение».
Издание монографии [1] соискателя «Байесовские сети: логико-вероятностный подход», СПб.: Наука, 2006 (в соавторстве с А. Л. Тулупьевым и С. И. Николенко), было поддержано грантом РФФИ Ж- 06-01-14108-д, а в 2007 г. её авторский коллектив стал лауреатом конкурса на лучшую научную книгу 2006 года (Фонд развития отечественного образования, г. Сочи).
Публикации. По теме диссертации опубликовано 64 научные работы, из них — 2 монографии (в соавторстве), прошедших научное рецензирование, одна из последних поддержана в 2006 г. издательским грантом РФФИ, 10 статей опубликованы в изданиях из «Перечня рецензируемых научных журналов», рекомендованных ВАК,
30 статей и докладов на конференциях, 13 зарегистрированных программ (в Роспа
тенте и ЦИТиС/ОФЭРНИО) и 9 тезисов научных конференций. Кроме того, часть
результатов включена в ряд отчётов по НИР и НИОКР.
Личный вклад А.В. Сироткина в ключевых публикациях с соавторами кратко характеризуется следующим образом. В монографиях [1,2] А.В. Сироткину принадлежат результаты, связанные со сложностью алгоритмов, выявлением структуры матрицы, участвующей в матрично-векторном уравнении локального апостериорно-
го вывода, построением контрпримеров, демонстрирующих различие интернальной и экстернальной степеней непротиворечивости ABC. Кроме того, ему принадлежит авторство алгоритма поддержания экстернальной непротиворечивости ациклической алгебраической байесовской сети и алгоритма построения алгебраической байесовской сети, являющейся семантически эквивалентным образом байесовской сети доверия с допустимыми (ненаправленными) циклами. А.В. Сироткину принадлежит формализация объемлющей непротиворечивости и решение задачи поиска наименьшей непротиворечивой оболочки. Наконец, в указанных монографиях приведены примеры программного кода, написанного А.В. Сироткиным.
В [4] А.В. Сироткину принадлежит обобщение метода пропагации детерминированного свидетельства на случай свидетельства, состоящего более чем из одного атома, в [6] — описание семантики различных степеней непротиворечивости ABC, в [8] — результат, связанный с выражением числа ребер в минимальном графе смежности, через ранг матроида, в [10] — выявление связи теоремы о множестве минимальных графов смежности и полнотой классификации владений. В [9] предложено улучшение алгоритма оценки наблюдаемой последовательности в скрытых марковских моделях на основе алгебраических байесовских сетей. В [12] — теорема 4 о непротиворечивой оболочке данных в общем случае.
В [3,5] А.В. Сироткин, используя индексацию объектов с помощью характеристических векторов, сформировал основу для алгебраизации синтеза согласованных оценок истинности и пропагации недетерминированных свидетельств.
Более подробное описание вклада А.В. Сироткина в совместные публикации содержится в тексте диссертации.
Структура и объём диссертации. Диссертация состоит из введения и четырёх глав, заключения, библиографии, списка листингов и приложения. Нумерация разделов, формул, примеров, лемм и теорем ведётся отдельно для каждой главы. Общий объем работы составляет 218 страниц. Список литературы содержит более 200 наименований.
Вероятностная логика
Одним из важных направлений исследований в области информатики является создание и изучение свойств моделей представления данных, сведений, знаний с неопределённостью. При этом важна как выразительная часть, то есть какие варианты данных и знаний и в каких областях могут быть представлены с помощью модели, так и возможность использования этой модели в комплексах программ. Развитие систем представления данных и знаний с неопределённостью при -17 — вело к выявлению ряда новых проблем. А. Л. Тулупьев в работе [60], обобщая мнение ряда исследователей, выделяет два так называемых «узких места»: представление данных и знаний с неопределённостью (uncertain knowledge representation bottleneck); дефицит данных и знаний (knowledge bottleneck).
Суть первой проблемы: как в формальных системах представить и систематически обрабатывать неопределённость (недоопреде-лённость) наших знаний, с которой зачастую приходится сталкиваться на практике. В [60] отмечается, что тривиальные решения, которые сводятся просто к тому, чтобы отбросить знания (или данные) с неполнотой, непригодны по двум причинам: во-первых, отнюдь не во -. всех предметных областях за разумное время можно получить «полные знания», во-вторых, человек способен действовать и в условиях неполноты знаний о складывающейся ситуации.
Вторая проблема заключается в отсутствии или неполноте знаний. Это может быть связано с тем, что не существует человека-эксперта, способного предоставить такие знания. Кроме того, не все эксперты готовы делиться своим знанием. Наконец, при попытках организовать машинное обучение (machine learning) по данным из баз данных нередко обнаруживается, что эти данные неполны и/или частично недостоверны (это может быть связано со способом получения данных, несовершенством приборов измерения и/или ошибок телеметрии). Борьбе с пропущенными данными посвящена, например, работа [201].
Существуют различные источники неопределённости. Так, например, неопределённость может возникать при анализе высказываний на естественном языке, при анализе статистических данных или работе со статистическими зависимостями, а также во многих других случаях. На данный момент существует несколько различных математических моделей неопределённости (неопределённости степени доверия к чему-то), среди них особо следует выделить следующие классы:
В диссертационной работе мы будем ориентироваться на второй тип неопределённости. Зачастую разница между вторым и третьим классами не видна, однако она существует. Во втором классе мера неопределённости того или иного события — это вероятность наступления такого события, тогда как в третьем случае это может быть не обязательно вероятностная, хотя и, скорее всего, близкая ей по природе мера. Примерами систем с третьим типом неопределённости являются теория Демпстера-Шеффера [106,134,188], меры необходимости и возможности [14,135,136; 174]. Кроме того, к третьему классу следует отнести системы MYCIN [2,152,165] и INFERNO [186]. Эти системы изначально эвристические по своей природе, однако для их описания можно предложить модель в рамках теории Демпстера-Шеффера [151]. Ко второму классу также близко исчисление инци-денций [116,117,168,169].
Кроме неопределённости на уровне данных, встречается и неопределённость на уровне обработки данных, например, системы с нечёткими правилами вывода [5,172], различные имитационные системы [15], динамические интеллектуальные системы [28].
Одна из существенных проблем обработки больших объёмов данных и знаний с неопределённостью — это невозможность полностью описать «мир», в котором мы действуем. Так, например, для вероят -19 ностной неопределённости таким «полным» описанием «мира» является единое общее распределение, заданное над всеми возможными означиваниями всех переменных. Но для 100 бинарных переменных такое описание, в общем случае, потребует задания 2100 скалярных оценок вероятностей. Поэтому возникают вопросы о том, когда описание общего «мира» можно получить (или восстановить либо явно, либо неявно) на основе небольшого набора данных и знаний. Конечно, это потребует различных дополнительных предположений. Принцип уменьшения необходимого количества данных и знаний (за счёт особенностей их структуры) для описания «мира» получил название «декомпозируемость знаний».
Оценки вероятностей над пропозициями
Над конъюнктами из N = supp [И] заданы совокупности оценок вероятностей; это совокупности образуются при совместном рассмотрении оценок вероятностей во всех фрагментах знаний, которые формируют алгебраическую байесовскую сеть N. В случае-скалярных оценок мы имеем набор {pi}J , а в случае интервальных оценок — {РгЙ=т\ Когда оценки на всех одинаковых конъюнктах, которые входят в два фрагмента знаний или более, совпадают, тогда можно говорить о том, что оценки определены как функция на носителе N. В скалярном случае эта функция будет иметь видр : N — [0;1], а в интервальном —
Определение 2.32 является наиболее общим из возможных. Однако при работе различных алгоритмов требуется некоторое упорядочивание ФЗ. Например, выделение пересекающихся между собой ФЗ. Подобные вещи достигаются за счёт задания вторичной структуры. Мы будем считать, что для АБС, с которыми мы работаем, вторичная структура уже задана. В настоящее время существует достаточно большое число работ, посвященных исследованию вторичной структуры [27,96-100]. Представление множества минимальных графов смежности в виде матроида [27] позволяет нам легко показать, что жадный алгоритм выкидывания «лишних» рёбер приведёт нас к графу смежности с минимально возможным числом рёбер. В работах [97-94] описываются алгоритмы, строящие множество всех возможных минимальных графов смежности. А в р5] затрагивается вопрос о построении других структур над множеством ФЗ, позволяющих характеризовать связи ФЗ между собой.
Вопросы, связанные с определением и поддержанием различных степеней непротиворечивости АБС, равно как и подходы к определе -66 нию непротиворечивости фрагмента знаний со скалярными и интервальными оценками истинности, ставились и изучались в ряде публикаций (в частности, в [9,12,51,53,64]); в настоящей работе мы в основном рассматриваем вопросы, касающиеся АБС со структурой дерева смежности.
Мы расположили данные степени непротиворечивости в порядке их «значимости». Но, к сожалению, более значимая степень непротиворечивости оказывается более вычислительно сложной. Чем выше степень непротиворечивости в нашем списке, тем сложнее ее проверить. Перейдём к формальным определениям [64].
Определение 2.38 АБС N = (N, р7 ) считается глобально непротиворечивой, если-ее с имеющимися оценками можно погрузить в непротиворечивый объемлющий фрагмент знаний и при этом оценки на формулах из АБС не изменятся:
ЗЄ = (С,р): (N cC)&(Consistent[e])&(VcGNp (c) =р[с)) Определение 2.39 АБС N = {(С р )}} считается интернально непротиворечивой, если для каждого конъюнкта из АБС для любого скалярного значения из интервала оценки ее истинности можно выбрать согласованные (т.е. совпадающие на одинаковых формулах) скалярные значения во всех фрагментах знаний, так, что все получившиеся ФЗ со скалярными оценками будут непротиворечивы:
Определение 2.40 ABC N = {(Cijpjjfzj1 считается экстернально непротиворечивой, если каждый фрагмент знаний в сети непротиворечив, а также оценки истинности каждой формулы, входящей одновременно в два фрагмента знаний или более, совпадают: ViVj(c є Q, с є С, =Ф pt(c) - pj(c)). Определение 2.41і ABC N = {(C Pi)} считается локально непротиворечивой, если каждый фрагмент знаний в сети непротиворечив:
Замечание 2.16 Локальная непротиворечивость не предъявляет требований к согласованности оценок на элементах, общих для двух или нескольких фрагментов знаний, но по сложившийся традиции мы все-таки считаем ее одной из степеней непротиворечивости сети.
Определения 2.38-2.41 даны в порядке убывания силы непротиворечивости. В монографии [64]. доказано, что из более сильной непротиворечивости всегда следует более слабая. В обратную же сторону утверждение неверно. В общем случае для любой пары существует пример алгебраической байесовской сети, на котором более слабая степень непротиворечивости есть, а, более сильной нет [85].
Теорема 2.8і (Контрпример, разделяющий экстернальную и ин-тернальнукь степени непротиворечивости.) Экстернальная и ин-тернальная степени непротиворечивости не совпадают.
Доказательство. Для доказательства данного утверждения достаточно построить алгебраическую байесовскую сеть, являющуюся экстернально непротиворечивой, но интернально противоречивой. Впервые примеры подобных сетей появляются в работах [31, 76].
Оставшийся ФЗ C{tiU]V)W} построен таким образом, что не суще-ствует вероятностного распределения, удовлетворяющего заданным оценкам и условиям p(t) = 0.6 и p(w) = 0.7 одновременно.
Пример сети, приведённой в теореме 2.11, экстер-нально согласуем (может быть сужен до экстернально непротиворечивой АБС), а интернально несогласуем. А это - более жёсткое разделение двух классов непротиворечивости. В качестве примера, разделяющего именно понятия непротиворечивости, достаточно рассмотреть часть сети, содержащую только два ФЗ с носителями С{ЧіГ 5), C{TiSit}, соответственно.
Следует заметить, что пример является ациклической АБС. Таким образом, хотя отсутствие циклов в АБС гарантирует эквивалентность глобальной и интернальной непротиворечивостей, оно не обеспечивает эквивалентности интернальной и экстернальной непротиворечивостей.
Вероятностная семантика байесовских сетей доверия
Алгоритм состоит из двух этапов. Первый этап, назовем его «сбор информации», — это строки 1-8 (шаги 1-4 в поясне нии). По окончании первого этапа мы получаем, что все ФЗ непротиво речивы, но, возможно, не все согласованы. Начнём «распространение информации» — «спуск» от корня к листьям. Рассмотрим текущий ФЗ и уточнение, пришедшее от его родителей. Заметим, что оценки, пришедшие от родителей, не могут быть шире, чем оценки в текущем ФЗ, это связано с тем, что на первом этапе «родителям» передавались оценки нашего ФЗ в качестве одного из ограничений, и, следовательно, как минимум такие ограничения выполнены. Таким образом, оценки, пришедшие от родителя, могут быть только уже. После поддержания непротиворечивости- оценки родителя не изменились, так как иначе алгоритм сообщил бы об особом случае. Следовательно, текущий ФЗ непротиворечив, и его оценки совпадают с оценками родителя. Рас смотрев в качестве «текущего» каждый ФЗ, получаем, что все ФЗ непротиворечивы и согласованы со своим родителем, а следователь но, любой общий элемент для двух ФЗ будет иметь одинаковые оценки в этих ФЗ.
Утверждение 3.4 Если в ациклической АБС все ФЗ пересекаются не более чем по одному элементу, то алгоритм 3.4 не сообщит об особом случае.
Доказательство. После этапа «сбора информации» все ФЗ являются непротиворечивыми. Если ФЗ непротиворечив, то при сужении оценки одного элемента можно будет уточнить все остальные оценки до непротиворечивых. Оценка, которую мы изначально сужаем, не изменится. Так как любая оценка из уточнённого интервала имела ре -92 ализацию, то весь уточнённый интервал будет входить в непротиворе чивый ФЗ. Таким образом, ситуация, когда на втором этапе алгоритма уточнится оценка в родительском ФЗ, невозможна.
Оценим сложность данного алгоритма. Нам потребуется провести процесс поддержания непротиворечивости ФЗ 2т — 1 раз. Будем считать, что количество атомов в г-том ФЗ — тц, а ФЗ, соответствующий узлу, являющемуся корнем дерева, имеет номер один, тогда надо решить: Для корня: 2(2П1 - 1) ЗЛП с 2Пі - 1 переменными, 2(2П1 - 1) граничными условиями и 2П ограничениями; Для остальных вершин: 4(2Пі — 1) ЗЛП с 2ти — V переменными, 2(2Пі — 1) граничными условиями и 2ти ограничениями.
Как мы уже отмечали, раньше, гц, сильно ограничены (на практике — не больше пяти), таким образом, мы получаем задачиг линейного программирования, вычислительная- сложность которых может быть оценена константой: По сравнению с процессом поддержания экс-тернальной непротиворечивости, потребуется решить примерно в два раза больше задач линейного программирования, но каждая из задач интернальной непротиворечивости — линейного размера, а каждая из задач экстернальной-непротиворечивости — константного размера. А, следовательно, поддержание экстернальной непротиворечивости будет вычислительно проще. Таким образом, в рассмотренном случае вычислительная сложность поддержания экстернальной непротиворечивости меньше, чем сложность поддержания интернальной непротиворечивости.
Для полноты картины осталось рассмотреть только локальную степень непротиворечивости. Для ее вычисления необходимо поддержать непротиворечивость каждого ФЗ. То есть решить 4(2 — 1) ЗЛП с 2Щ — 1 переменными, 2(2Пі — 1) граничными условиями и 2Пі ограничениями. Замечание 3:5 Важно то, что если сеть противоречива, то для случая интернальной и глобальной непротиворечивости это выявится при решении первой же ЗЛП, и, в таком случае, все остальные ЗЛП решать уже не потребуется.
Основу байесовской сети доверия составляют два объекта. Первый — это ациклический направленный граф. Второй — это набор распределений (тензоров) условных вероятностей, заданных для каждой из вершин графа. Начнём с первого объекта и ряда связанных с ним вопросов, после чего перейдём ко второму. Более подробное описание аппарата байесовских сетей доверия представлено в [64,85,128,159,163;175,183].
Определение 3.1 Ациклический направленный граф— это направленный граф, в котором нет направленных циклов.
Заметим, что в монографии [183] основоположник аппарата байесовских сетей доверия Дж. Пиерл отказывается от любых циклов — и от направленных, и от ненаправленных, — работая только с полидеревьями. Однако циклы встречаются в практических задачах, например в турбокодировании [173]/И других [102 , 125], поэтому современные исследователи не отказываются от ненаправленных циклов, но при этом оговаривают, что происходит усложнение алгоритмов обработки [159].
Ациклический-направленный граф используется для того, чтобы представить непосредственные причинно-следственные связи между переменными, лежащими в смежных вершинах графа.
Реализация фрагмента знаний
Рассмотрим происходящее на листинге 4.22. Строки 2-6 описывают исходную скрытую марковскую модель. Pi — задаёт априорное распределение скрытого состояния. В — задаёт условные вероятности значения скрытого состояния при условии заданного состояния на предыдущем шаге. Obs — задаёт условные вероятности значения наблюдаемых переменных при заданных скрытых состояниях. Массив Evid — задаёт наблюдаемые состояния, а Т — .определяет число шагов в модели. Задача приведённой здесь функции — сообщить, какова вероятность получить заданные значения наблюдаемых переменных.
Строки 8-12 задают необходимые переменные. После чего в строках 14-29 моделируется первичная пропагация, необходимая для формирования оценок в ФЗ.
После получения оценок ФЗ можно перейти к реализации алгоритма вычисления вероятности получить заданные наблюдения. Соответствующий код приведён на листинге 4.23. Строка 4 отвечает за вычисление вероятности наблюдать заданные состояния в момент времени і и позже. Строчки 5-6 отвечают за пропагацию заданного наблюдения в ФЗ, включающем данную переменную. Строки 7-12 обеспечивают распространение этого свидетельства по всей сети. В строке 14 производится вывод результата.
После запуска программы мы получили результат 0.101736, который соответствует В статье [29] доказывается, что нет необходимости распространять свидетельство на всю сеть. Достаточно распространить его на ФЗ, содержащий переменную-наблюдение на предыдущем шаге. Этого легко добиться, заменив 7 строку j = і-і; Проверка необходима, чтобы избежать выхода за границы заданных ФЗ. Результаты запуска двух вариантов показывают одни и те же значения, что соответствует доказанному в [29]. Кроме рассмотренного здесь моделирования определённого класса скрытых марковских моделей, АБС могут применяться так для представления сложных связей разного рода, например, для характеризации популяции в генетических алгоритмах [50] или социальных систем [61].
В этой главе мы описали прототип комплекса программ, реализующий основные алгоритмы локального логико-вероятностного вывода и поддержания различных степеней непротиворечивости АБС, привели примеры использования созданной библиотеки. Результаты работы прототипа полностью совпали с предсказываемыми теорией, из чего можно сделать вывод о корректности кода. Созданный прототип библиотек может быть встроен в другое программное обеспечение, что демонстрируется на примере моделирования скрытых марковских моделей в разделе 4.6. Прототип комплекса программ был зарегистрирован в РОСПАТЕНТЕ, ОФЕРНиО и ЦИТиС. Копии свидетельств приведены в приложении.
На защиту выносятся следующие основные результаты диссертационного исследования: 1) разработан алгоритм вычисления элементов матрицы, со ответствующей1 линейному оператору ненормированного локального апостериорного вывода в случае детерминированного свидетельства, на основе выражения ее через фиксированные «элементарные» мат рицы малой размерности; 2) построен контрпример АБС, являющейся экстернально непротиворечивой, но не являющейся интернально непротиворечивой; 3) получены оценки сложности алгоритмов локального логико-вероятностного вывода (поддержание непротиворечивости, априорный вывод, апостериорный вывод); 4) получены оценки сложности алгоритмов поддержания различных степеней непротиворечивости АБС (глобальной, интернальной, экстернальной); 5) сформирована математическая модель согласования противоречивых данных на основе понятия «накрывающая непротиворечивость»; 6) разработан алгоритм построения АБС, семантически эквивалентной заданной БСД, на основе представления последней в виде дерева смежности; 7) исследована устойчивость процесса поддержания непротиворечивости ФЗ АБС; 8) разработан комплекс программ на языке C++, обеспечивающий локальный логико-вероятностный вывод в АБС, а так же поддержание различных степеней непротиворечивости для АБС, представленной в виде дерева смежности. .
