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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ТУЛУПЬЕВ Александр Львович

АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ: ЛОГИКО-ВЕРОЯТНОСТНАЯ ГРАФИЧЕСКАЯ МОДЕЛЬ БАЗ ФРАГМЕНТОВ ЗНАНИЙ С НЕОПРЕДЕЛЕННОСТЬЮ

05.13.17 — Теоретические основы информатики

На правах рукописи

с/

ОС1347ЭЭ24

А В Т О Р Е Ф Е РАТ

диссертации на соискание ученой степени доктора физико-математических наук

1 5 ОПТ ?г

С анкт-Петербург 2009

003479924

Работа выполнена в лаборатории прикладной информатики Учреждения Российской академии наук Санкт-Петербургский институт информатики и автоматизации РАН.

Официальные оппоненты: доктор физико-математических наук,

профессор ВАРАНОВ Сергей Николаевич (ЗАО «Моторола ЗАО»),

доктор физико-математических наук, профессор ХОВАНОВ Николай Васильевич (Санкт-Петербургский государственный университет),

доктор физико-математических наук, профессор ЯЗБНИН Александр Васильевич (Тверской государственный университет)

Ведущая организация Учреждение Российской академии наук

Институт системного анализа РАН

2 6.1 1.2009 1 5 - 3 0з

Защита состоится «_»_ 2009 г. в часов на заседа-

нии совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 28, математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

д . 2 9, 0 9.2009 9ПП0

Автореферат разослан «_»_ 2009 г.

Ученый секретарь диссертационного совета

Даугавет И.К.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Подводя итоги одного из этапов многолетнего изучения моделей знаний с неопределенностью, В.И. Городецкий в 1993 г. ввел в область исследований искусственного интеллекта (ИИ) алгебраические байесовские сети (АБС) как новую парадигму экспертных систем [1].

Источником особого научного интереса к указанным моделям послужил анализ проблем, существенно замедляющих прогресс в области масштабных промышленных внедрений экспертных систем. Выли выявлены, в частности, два вида дефицита: дефицит математических моделей для представления знаний с неопределенностью (uncertain knowledge representation bottleneck) и просто дефицит знаний (knowledge bottleneck) [10,20]. Интенсивно развивающиеся в рамках ИИ теории вероятностных графических моделей.1 (ВГМ) вносят существенный вклад в поиск и разработку путей преодоления дефицита двух указанных видов, а также ряда смежных проблем.

Теории ВГМ [1,3, 6-11,14,15] предлагают как новые модели для представления систем знаний с неопределенностью, т.е. позволяют смягчить влияние дефицита первого вида, так и новые подходы :с алгоритмизации машинного обучения (machine learning, синоним — автоматическое обучение) таких моделей на основе накопления и обработки разнородных исходных данных, сведений или знаний с неопределенностью (в частности, отличающихся неполнотой, неточностью или имеющих нечисловой харахтер). Машинное обучение позволяет обойти ряд препятствий, создаваемых дефицитом второго вида. Помимо этого, в теориях ВГМ с помощью методов математики и информатики исследуются предложенные модели данных и знаний с неопределенностью, принципы создания и функционирования программных средств, позволяющих представить эти модели в памяти компьютера, а также автоматизировать процессы их формирования, хранения, обработки и обучения.

К ВГМ, нацеленным з первую очередь на решение очерченных и ряда смежных проблем, в рамках искусственного интеллекта можно причислить байесовские сети доверия (их ввел J. Pearl) [3,7,10,11,15,18-20], в некоторой степени — марковские сети (были «импортироьаны» из статистической физики, где классическим примером их применения является модель Изинга в изучении магнетизма) [8,19], а также алгебраические байесовские сети (введены В. И. Городецким) [1]). Следует отметить, что в теории байесовских сетей доверия (ВСД) остаются открытыми вопросы, связанные с обработкой направленных циклов и интервальных оценок вероятностей; кроме того, вероятностный вывод не может осуществляться непосредственно в ВСД с многосзязной структурой — такую сеть требуется предварительно преобразовать в дерево сочленений.

Теория алгебраических байесовских сетей занимает свое место среди теорий ВГМ и решает общие с ними задачи, а сами алгебраические байесовские сети имеют ряд отличительных особенностей и в первую очередь могут быть охарактеризованы как логико-вероятностные графические модели (ЛВГМ) баз фрагментов знаний (ВФЗ) с неопределенностью [17,18,20,26].

1 Термин вероятностные графические модели является переводом англоязычного probabilistic graphical models. Нельзя не признать, что в русском языке термин графическая модель воспринимается, скорее, как визуальная модель, например как чертеж, схема или эскиз. В силу этого подчеркнем, что в настоящем диссертационном исследовании термин графические модели обозначает математические модели, основу которых составляют графы.

Ключевой принцип, лежащий в основе ВГМ, хорошо известен — это принцип декомпозиции. Он применяется к совокупности знаний о предметной области. Считается, что эксперт может достаточно детально охарактеризовать связи между двумя-тремя-четырьмя утверждениями о предметной области [15] — в каком-то смысле получается «фрагмент знаний» (ФЗ). Таких фрагментов знаний много, они образуют БФЗ. Однако фрагменты знаний и их базы нельзя напрямую заложить в интеллектуальную информационную систему или комплекс программ. Сначала требуется рассмотреть математические модели ФЗ и БФЗ, разработать соответствующие структуры данных и снабдить их алгоритмами обработки. Получающиеся модели должны обладать некоторой «регулярностью» структуры, общностью принципов построения своих элементов, чтобы можно было использовать одни и те же алгоритмы вывода как на локальном уровне (т.е. на уровне фрагментов знаний), так и на глобальном (т.е. на уровне всей базы).

С математической точки зрения возникающие объекты могут быть рассмотрены как система случайных элементов, которая, как правило, организована в виде графа со специфическими свойствами или решетки (отсюда — графическая модель). Случайные элементы в системе могут быть связаны друг с другом, оказывать влияние на означивания других случайных элементов; однако связи между ее компонентами предполагаются достаточно редкими, немногочисленными, разреженными (sparse) [3,7,15].

Декомпозиция системы знаний дает преимущества и на психологическом (экспертном или пользовательском) уровне, поскольку получающаяся математическая модель структурирована и обозрима, и на технологическом, поскольку уменьшаются необходимые для хранения модели объемы памяти и вычислительная сложность алгоритмов ее обработки как на локальном, так и на глобальном уровне. Структурированность и обозримость ВГМ также видятся ее преимуществами при представлении сложных связей, выявленных классическим статистическим анализом или интеллектуальным анализом данных (data mining) [10,11,20].

Особый интерес с точки зрения моделирования процесса размышлений (reasoning) [6,9,14] специалиста-эксперта представляет логико-вероятностный подход, в котором моделью утверждения являются пропозициональные формулы (заданные над определенным алфавитом), что традиционно для формальной логики, а степень уверенности в истинности (или стохастическая неопределенность истинности) этих пропозициональных формул и сила связей между ними характеризуются с помощью оценок вероятностей: как скалярных (точечных), так и интервальных.

В своем современном виде логико-вероятностный подход был достаточно последовательным образом внесен в область исследований искусственного интеллекта Н. Нильссоном [12] и развит Фейгиным, Хальперном и Мегги до [4,5]. Приоритет Н. Нильссона, как он сам отмечает [13], был неоднократно оспорен. Анализируя позиции сторон спора о приоритетах, нельзя упускать из виду того, что еще в 1854 г. Дж. Буль [2] пытался применить вероятность как меру истинности (или как степень доверия к истинности) пропозициональных формул. Он сформулировал ряд проблем, которыми занимаются исследователи в области вероятностной логики и неопределенности в искусственном интеллекте по сей день.

Хотя логико-вероятностный подход имеет .длительную историю, остается актуальным решение комплекса проблем, нацеленных на его применение в интеллектуальных информационных системах: сначала требуется разработать в рамках указанного подхода математические модели (допускающие интервальные оценки вероятности истинности) ВФЗ с неопределенностью с тем, чтобы по ним, в свою очередь, можно было бы построить структуры данных для представления накопленных знаний; затем автоматизировать ряд операций логико-вероятностного вы-

вода: проверка и поддержание непротиворечивости ФЗ и ВФЗ, априорный вывод во фрагменте знаний, апостериорный вывод (распространение влияние свидетельства) в ФЗ и ВФЗ; наконец, исследовать сформированные модели и структуры данных, а также обосновать корректность и изучить некоторые свойства как разработанных методов формирования непротиворечивых ФЗ и ВФЗ, вывода априорных и апостериорных оценок в них, так и получаемых с помощью указанных методов результатов.

Объект исследования — алгебраические байесовские сети, представляющие собой, с одной стороны, набор идеалов конъюнктов со скалярными или интервальными оценками вероятности истинности, причем указанный набор идеалов структурирован как граф смежности, а с другой стороны, логико-вероятностную графическую модель баз фрагментов знаний со стохастической (вероятностной) неопределенностью.

Цель исследования — на основе логико-вероятностного подхода к представ-

лению неопределенности в интеллектуальных системах, предложенного Н. Нильс-соном, развить теорию алгебраических байесовских сетей как математических моделей знаний с вероятностной неопределенностью, допускающих декомпозицию на фрагменты ограниченного размера, для формирования научных основ современных информационных технологий, позволяющих решить проблему автоматизации логико-вероятностного вывода в указанных сетях. Для достижения указанной цели необходимо решить следующие основные задачи:

1) формализовать с использованием логико-эероятностного подхода в рамках теории ABC математические модели фрагмента знаний, базы фрагментов знаний и свидетельства, а также выявить вероятностную семантику этих объектов посредством анализа взаимосвязи входящих в них оценок вероятностей конъюнктов и дискретной плотности вероятности на соответствующем конечном вероятностном пространстве;

2) сформировать систему понятий, характеризующих состояние непротиворе-. чивости фрагмента знаний и ABC; раскрыть отношения этих состояний; разработать методы их проверки и поддержания как в локальном, так и в глобальном случае (для интернальной и глобальной степеней непротиворечивости АБС), а также проанализировать влияние операций построения линейной комбинации и линейной оболочки на указанные состояния непротиворечивости;

3) формализовать локальный априорный вывод, проанализировать его взаимосвязь с поддержанием непротиворечивости, разработать метод локального априорного вывода в случае формулы, представленной в виде совершенной дизъюнктивной нормальной формы (СДНФ), и метод анализа чувствительности его результата к допустимым вариациям исходных данных в случае скалярных оценок;

4) формализовать апостериорный вывод; разработать метод реализации его локального варианта в случае детерминированного свидетельства и обобщить полученный результат для двух других видов свидетельств; исследовать чувствительность ненормированного результата локального апостериорного вывода по детерминированному свидетельству в случае скалярных оценок; исследовать результаты локального апостериорного вывода с точки зрения их непротиворечивости при непротиворечивых исходных объектах; разработать метод распространения влияния стохастического свидетельства в ациклической АБС со скалярными оценками на основе «передачи» виртуальных свидетельств; выявить предположения о вероятностной семантике такой ABC, на которые опирается указанный метод, оценить сложность алгоритмов, его реализующих;

5) разработать метод преобразования ациклической байесовской сети доверия со случайными бинарными элементами в узлах в ациклическую алгебраическую байесовскую сеть; выявить отношение их вероятностных семантик;

6) проанализировать вероятностную семантику цикла смежности фрагментов знаний в ABC, разработать методы его преобразования в цепь смежности и проверки его непротиворечивости; с помощью полученных результатов выявить вероятностную семантику направленного цикла в теории ВСД (ВСД-цикла) и разработать для такого цикла метод проверки его непротиворечивости;

7) формализовать две альтернативные математические модели фрагментов знаний (на основе идеала дизъюнктов и набора квантов), разработать метод проверки и поддержания их непротиворечивости;

8) спроектировать и реализовать комплекс программ для проведения вычислительных экспериментов с исследованными в диссертации операциями логико-вероятностного вывода в ABC и их фрагментах, а также разработать структуру реляционной базы данных, ориентированную ва хранение ABC, фрагментов знаний, свидетельств и результатов логико-вероятностного вывода.

Выбор вероятностной семантики исследуемых в диссертационной работе объектов теории АБС, определений и методов выполнения операций логико-вероятностного вывода, получения оценок чувствительности ограничивается дополнительным требованием, выражающимся в том, чтобы все возникающие в процессе логико-вероятностного вывода экстремальные задачи допускали сведение к решению задачи (или серии задач) линейного программирования.

Методы исследования. В обзорно-аналитической и теоретической частях исследования используются объекты и методы алгебры (линейной алгебры, теории частично упорядоченных множеств, булевой алгебры), теории вероятностей и вероятностной логики, теории графов, экстремальных задач (задачи линейного и гиперболического программирования), комбинаторики, мягких вычислений (преимущественно различные «меры» истинности), а также элементы теории марковских цепей и метода Монте-Карло. В программно-технологической части исследования используются теория реляционных баз данных, принципы структурного и объектно-ориентированного программирования (как в разработке структур данных, так и в реализации кода), а также ряд технологий, связанных с языком реализации (Java), средой разработки (NetBeans), СУБД (JavaDB). Само диссертационное исследование по своему объекту и методам, использованным для решения ряда задач по построению моделей и обработке знаний с вероятностной неопределенностью, относится к разделу искусственного интеллекта, изучающему и развивающему средства представления знаний.

Научная новизна. В диссертации формализована и исследована новая логико-вероятностная графическая модель баз фрагментов знаний с неопределенностью — алгебраические байесовские сети, чья глобальная структура задается в виде графа смежности (или его подвидов: дерева смежности, цепи смежности, цикла смежности), в узлах которого расположены идеалы конъюнктов со скалярными или интервальными оценками вероятности истинности, что отличает указанную модель от других вероятностных графических моделей (в частности, от байесовских сетей доверия и марковских сетей) и позволяет с ее помощью представлять, агрегировать и обрабатывать знания с неопределенностью посредством ряда операций логико-вероятностного вывода: поддержания и проверки непротиворечивости, априорного вывода, апостериорного вывода, причем в последнем допускается использование как детерминированных свидетельств, так и стохастических и неточных свидетельств, компоненты которых могут быть зависимыми.

Осуществлен вывод матрично-векторных уравнений, связывающих оценки вероятностей элементов идеала конъюнктов с дискретной плотностью вероятности соответствующего конечного вероятностного пространства, что позволило, в свою очередь, разработать и описать на матрично-векторном языке методы проверки и поддержания непротиворечивости фрагмента знаний ABC, априорного и

апостериорного выводов в нем и исследовать чувствительность результатов двух последних, а также обобщить указанный метод проверки и поддержания непротиворечивости на фрагменты знаний с альтернативной структурой.

Разработаны методы глобального логико-вероятностного вывода в ABC, позволяющие проверять и поддерживать интеряальную и глобальную степени непротиворечивости ABC (причем указаны условия, при которых интернальная степень непротиворечивости обеспечивает глобальную степень непротиворечивости), а также позволяющие распространить влияние стохастического свидетельства, поступившего во фрагмент знаний ациклической алгебраической байесовской сети со скалярными оценками, на другие входящие в нее ФЗ; получены оценки вычислительной сложности соответствующих алгоритмов.

Обнаружено и формально обосновано свойство сохранения состояния непротиворечивости фрагментов знаний и степеней непротиворечивости алгебраических байесовских сетей по отношению к операциям линейной комбинации и линейной оболочки. Кроме того, доказано, что линейная оболочка будет единственным минимальным (по вхождению оценок-интервалов) результатом операции «накрывающей» непротиворечивости, примененной к совокупности непротиворечивых фрагментов знаний (или отвечающих требованиям заданной степени непротиворечивости алгебраических байесовских сетей) одинаковой структуры.

Выявлена вероятностная семантика и предложен метод преобразования направленного цикла байесовской сети доверия а цикл смежности и цепь смежности фрагментов знаний АБС, что, в свою очередь, позволило разработать метод проверки непротиворечивости исходного цикла; получены оценки вычислительной сложности соответствующих алгоритмов. Разработан метод преобразования ациклической байесовской сети доверия с бинарными случайной элементами в узлах в ациклическую алгебраическую байесовскую сеть.

На языке Java и с использованием java-технологий спроектирован и реализован комплекс программ, позволяющий выполнять исследованные в диссертации операции логико-вероятностного вывода с ABC, их фрагментами и свидетельствами с целью проведения вычислительных экспериментов; кроме того, на основе реляционной СУБД JavaDB реализована база данных, ориентированная на хранение указанных объектов и результатов логико-вероятностного вывода.

Все основные научные результаты, полученные в процессе диссертационного исследования и выносимые на защиту, являются новыми.

Диссертациониое исследование выполнялось согласно планам СПИИРАН по научному направлению «Теоретические основы построения информационных технологий для интеллектуальных систем автоматизации научных исследований, управления, производства и других сфер деятельности».

Апробация.Результаты диссертационного исследования докладывались и об-

суждались на следующих научных мероприятиях:

1) Международная конференция «Знания-Диалог-Решение-95», Ялта, 1995; 2) IV Санкт-Петербургская международная конференция «Региональная ипформатика-95», Санкт-Петербург, 1995; 3) Всероссийская научно-техническая конференция «Электроника и информатика», Москва, 1995; 4) Международная конференция «Эволюция ин-фосферы-95», Москва, 1995; 5) Шестая национальная конференция по искусственному интеллекту с международным участием КИИ'98, Пущико, 1998; 6) VII Санкт-Петербургская международная конференция «Региональная йнформатика-2000 (РИ-2000)», Санкт-Петербург, 2000; 7) Международный научно-практический семинар «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 2001; 8) Всероссийская научно-практическая конференция «Информатика и информационные технологии в образовании», Санкт-Петербург, 2001; 9) XI Межгосударственная школа-семинар «Синтез и сложность управляющих систем», Москва, 2001; 10) Международный банковский конгресс и Международная научно-практическая конференция, Санкт-Петербург, 2001; 11) Международная научная школа «Моделирование и анализ безопас-

ноетя и риска в сложных системах», Санкт-Петербург, 2002; 12) Всероссийская научно-практическая конференция «Информатика и информационные технологии в образовании», Санкт-Петербург, 2002; 13) Научная сессия МИФИ-2002, Москва, 2002; 14) VIII Санкт-Петербургская международная конференция «Региональная информатика-2002», Санкт-Петербург, 2002; 15) IX Санкт-Петербургская международная конференция «Региональная информатика-2004», Санкт-Петербург, 2004; 16) Научная сессия МИФИ-2005, Москва, 2005; 17) III Международный научно-практический семинар «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Пущина, 2005; 18) Mexican International Conference on Artificial Intelligence, Mexico, 2005; 19) Конференция «Мягкие вычисления и измерения», Санкт-Петербург, 2005; 20) Всероссийская научная конференция по нечетким системам и мягким вычислениям," Тверь, 2006; 21) Научная сессия МИФИ-2006, Москва, 2006; 22) X Санкт-Петербургская международная конференция «Региональная информатика - 2006», Санкт-Петербург, 2006; 23) Научная конференция МИФИ-2007, Москва, 2007; 24) Международная конференция по мягким вычислениям и измерениям — 2007; Санкт-Петербург, 2007; 25) IV Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 2007; 26) V Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России», Санкт-Петербург, 2007; 27) Научная сессия МИФИ-2008, Москва, 2008; 28) Научная конференция «Информационные технологии и системы-2008», Геленджик, 29 сентября — 03 октября, 2008 г.; 29) Вторая Всероссийская научной конференции с международным участием «Нечеткие системы и мягкие вычисления» (НСМВ-2008), г. Ульяновск, 2729 октября 2008 г.; 30) XI Санкт-Петербургская международная конференция «Региональная информатика - 2008», Санкт-Петербург, 2008; 31) Научная сессия МИФИ-2009, Москва, 2009; 32) Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009), Коломна, 26-27 мая 2009 г.; 33) V Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 28-30 мая 2009 г.; 34) Международная конференция по мягким вычислениям и измерениям SCM-2009, Санкт-Петербург, 25-27 июня 2009 г.; 35) Санкт-Петербургский городской научный семинар «Информатика и компьютерные технологии» (многократно в 1996-2001 и 2004-2009 гг.).

Достоверность полученных в диссертационном исследовании результатов обоснована корректностью применения методов соответствующих математических дисциплин. Дополнительным аргументом в пользу достоверности результатов диссертационного исследования является работоспособность комплекса программ, реализующего операции логико-вероятностного вывода в алгебраических байесовских сетях и их фрагментах.

Теоретическая и практическая значимость исследования. Реализация результатов работы. Диссертация носит преимущественно теоретический характер. Модели и методы, разработанные в ней, позволят спроектировать и реализовать средства представления знаний со стохастической (вероятностной) неопределенностью в интеллектуальных системах и комплексах программ. При этом реализация таких комплексов облегчается тем, что они могут использовать уже существующие программные технологии и библиотеки программ (в частности, библиотеки для решения задач линейного программирования). В процессе исследования для проведения численных экспериментов был разработан комплекс программ, позволяющий представить и обработать объекты, а также выполнить операции логико-вероятностного вывода, описанные в диссертации. (Компоненты комплекса зарегистрированы; копии регистрационных документов помещены в приложение к диссертации.)

Второй составляющей теоретической и практической значимости является возможность исследовать на непротиворечивость и обработать структуры, недопустимые в рамках теории байесовских сетей доверия, но возникающие на практике (направленные циклы). С теоретической точки зрения важен результат о невозможности построения исчисления байесовских сетей доверия, одновременно

допускающего обработку направленных циклов и сохраняющего традиционную вероятностную семантику байесовских сетей доверия (единственность глобального распределения и согласованность с ним тензоров условных вероятностей в узлах сети).

Третьей составляющей практической значимости полученных теоретических результатов является возможность их применения в альтернативном способе расчетов надежности фрагментов структурно-сложных систем или для оценки надежности таких фрагмептов в случае интервальных исходных данных и в случае недоопределенных, но реально существующих или потенциально возможных зависимостей между выходами из строя элементов, ранее полагавшихся независимыми. (Имеется акт о внедрении от ОАО СПИК СЗМА; копия акта помещена в приложение к диссертации.)

Четвертой составляющей практической значимости является возможность применения теории алгебраических байесовских сетей и разработанного комплекса программ в решении задач поддержки принятия решений, в частности для представления и обработки неточной, неполной, нечисловой информации о соотношении вероятностей истинности утверждений, на основе которых принимаются решения, и для комбинирования или агрегирования такой информации из источников, степени доверия к которым могут различаться или быть неизвестными.

Наконец, важной составляющей практической значимости является использование теории алгебраических байесовских сетей в преподавании дисциплин, посвященных научным основам современных информационных технологий и подходам к разработке интеллектуальных систем, в вузах, где осуществляется подготовка студентов и аспирантов соответствующих специальностей. (Имеются акты об использовании в учебном процессе от СПбГУ и от СПбГУ ИТМО; копии актов помещены в приложение к диссертации.)

Дополнительным свидетельством реализации результатов диссертационного исследования, а также аргументом в пользу его научной значимости и актуальности служит поддержка, полученная соискателем в форме стипендий и грантов. Исследования по теме диссертации были дважды поддержаны Государственной стипендией для талантливых молодых ученых (1998-2000, 2000-2002), четырежды — грантом Фонда содействия отечественной науке по программе «Молодые кандидаты и доктора наук. Выдающиеся учёные РАН» (2004, 2005, 2006, 2007), грантом РФФИ (09-01-00861-а — «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью») и, наконец, госконтрактом 02.442.11.7289 от 28.02.2006 на выполнение НИР «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логико-вероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой» в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы».

Издание монографии [18] соискателя «Байесовские сети: логико-вероятностный подход» (СПб.: Наука, 2006; в соавт. с С. И. Николенко и А. В. Сиротки-ным) было поддержано грантом РФФИ № 06-01-14108-д, а в 2007 г. ее авторский коллектив стал лауреатом конкурса на лучшую научную книгу 2006 года (Фонд развития отечественного образования, г. Сочи).

Публикации. По теме диссертации опубликовано 88 научных работ, из них 5 монографий (3 единоличные и 2 в соавторстве), прошедших научное рецензирование, 10 статей в изданиях из «Перечня ведущих рецензируемых научных журналов и изданий», 64 научные статьи и доклада на конференциях, 9 зарегистрированных программ для ЭВМ. Сверх указанного по теме диссертации было

опубликовано 2 учебных пособия, тахже прошедших научное рецензирование, и ряд тезисов научных докладов.

Личный вклад А.Л. Тулупьева в публикациях с соавторами характеризуется следующим образом.

В совместных публикациях с В.И. Городецким, в том числе в [21], А.Л. Тулупье-ву принадлежит анализ свойств обсуждаемых в статьях объектов (преимущественно алгебраических байесовских сетей, их фрагментов, а также непротиворечивости этих объектов), а В.И. Городецкому — содержательная постановка задач, примеры и указание возможных приложений обсуждаемых формализмов и объектов для решения задач искусственного интеллекта в области инженерии знаний.

В монографиях [18,20] А.Л. Тулупьеву принадлежат все результаты, характеризующие вероятностную семантику алгебраических байесовских сетей и их фрагментов, уравнения и методы локального и глобального логико-вероятностного вывода в алгебраических байесовских сетях, результаты о линейкой комбинации и линейной оболочке алгебраических байесовских сетей и их фрагментов знаний, формализация операции «накрывающей» непротиворечивости, результаты о «накрывающей» непротиворечивости в части, относящейся к совокупности непротиворечивых объектов, анализ вероятностной семантики циклов в алгебраических байесовских сетях и байесовских сетях доверия, методы преобразований и обработки этих циклов, определения и анализ свойств степеней непротиворечивости АБС, алгоритмы проверки и поддержания интернальной и глобальной степени непротиворечивости этих сетей, результат о невозможности обработать направленный цикл в байесовской сети с «традиционной» вероятностной семантикой, обобщения алгебраических байесовских сетей на другие формализмы, позволяющие приписывать пропозициональным формулам оценки истинности, подход к анализу чувствительности локальных априорного и апостериорного выводов (в том числе посредством исследования соответствующих матрично-векторных уравнений), формализация задач, проектирование программ и реализация структур данных в них, определение различных видов свидетельств, анализ их вероятностной семантики, алгоритмы их обработки и распространения в АБС, анализ и алгоритм преобразования ациклической байесовской сети доверия в алгебраическую байесовскую сеть, исследование взаимосвязи априорного вывода и поддержания непротиворечивости, определение, анализ вероятностной семантики расширенного фрагмента знаний и фрагментов знаний с альтернативной структурой, матрично-векторные уравнения и алгоритмы проверки и поддержания их непротиворечивости и априорного вывода в таких фрагментах знаний, а также диссертантом предложены уравнения и алгоритмы для локального машинного обучения алгебраических байесовских сетей, алгоритм восстановления вторичной структуры алгебраической байесовской сети по ее первичной структуре. На основе полученных А.Л. Тулупьевым результатов A.B. Сироткин выявил структуру матрицы, участвующей в матрично-векторЕОм уравнении локального апостериорного вывода, привел теоретические оценки устойчивости поддержания непротиворечивости, реализовал часть программного кода, привел дискриминант-пример, разделяющий интернальную и экстернальную степени непротиворечивости алгебраических байесовских сетей, разработал алгоритм построения алгебраической байесовской сети, являющейся семантически эквивалентным образом байесовской сети доверия с допустимыми (ненаправленными) циклами, разработал алгоритм поддержания экстернальной непротиворечивости ациклической алгебраической байесовской сети, уточнил формализацию объемлющей непротиворечивости и исследовал ее в случае противоречивых исходных данных. С.И. Николенко сосредоточился на работе с байесовскими сетями доверия в аспектах, не входящих в объект диссертационных исследований A.A. Тулупьева и A.B. Сироткина. Такое же соотношение тематики результатов к вкладов (в их релевантной каждой конкретной работе части) сохранялось во всех совместных публикациях с A.B. Сироткиным и С.И. Николенко, в частности, в [23—26], а также в совместных работах с другими соавторами. Более подробная характеристика личного вклада А.Л. Тулупьева содержится в тексте диссертации.

Структура и объем работы. Диссертация состоит из введения, 7 глав, заключения, перечня сокращений, библиографии, списка таблиц, иллюстраций и примеров, а также предметного указателя и приложений. Общий объем работы составляет 670 страниц. Библиография содержит более 450 наименований. В приложения вынесены часть примеров, копии регистрационных документов и актов о внедрения (использовании), а также иной материал, являющийся справочным, иллюстративным или дополняющим основной.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

В автореферате воспроизводяся лишь ключевые объекты (определения, обозначения, теоремы, предложения, формулы и проч.), их нумерация самостоятельная и может не совпадать с таковой в диссертации.

Во введении дается общая характеристика работы: обосновывается актуальность темы диссертации; указывается объект, а также формулируются цель и основные задачи исследования; приводятся его методы; характеризуются научная новизна полученных результатов, их апробация, теоретическая и практическая значимость исследования; сообщаются сведения о реализации результатов работы, основных публикациях, структуре и объеме диссертации.

Глава 1 «Модели знаний и системы с неопределенностью в ИИ» посвящена обзору и анализу широкого контекста исследований, связанных с представлением знаний с неопределенностью в интеллектуальных системах. Сначала рассматриваются классические экспертные системы (MYCIN, PROSPECTOR, INFERNO), затем — различные меры неопределенности истинности (степени доверия к истинности) утверждений (вероятностная мера истинности, нечеткие меры истинности, меры доверия и правдоподобия, меры необходимости и возможности), исчисление инциденций, и, наконец, формируется система аргументов в пользу необходимости обработки не только скалярных (точечных), но и интервальных оценок степеней доверия. Среди степеней доверия преимущество отдается вероятностной мере истинности. Приводятся примеры различных математических моделей баз фрагментов знаний с неопределенностью, среди них — байесовские и марковские сети.

Результаты предпринятого анализа обосновывают цель, задачи и выбор основного объекта исследования — алгебраических байесовских сетей, которые обладают как общими преимуществами вероятностных графических моделей для представления знаний с неопределенностью, допускающих декомпозицию, так и рядом отличительных особенностей: 1) ABC основываются на логико-вероятностном подходе, позволяющем сочетать преимущества формальной логики для представления знаний в виде системы пропозициональных формул и теории вероятности для характеристики неопределенности их истинности; 2) в них четко различаются три основные набора операций (проверка и поддержание непротиворечивости, априорный вывод, апостериорный вывод) логико-вероятностного вывода; 3) ABC позволяют моделировать свидетельство с зависимыми компонентами; 4) в них можно использовать как скалярные, так и интервальные оценки вероятности истинности. Кроме того, сведения, накопленные в байесовской сети доверия (ВСД), можно представить в ABC, а также с помощью ABC объяснить [19,20,301, почему до сих пор не разработано ВСД-исчисление, позволяющее обрабатывать байесовские сети доверия с направленными циклами [7,15].

Глава 2 «Байесовские сета доверия» вводит указанные сети как ациклический направленный граф с тензорами условных вероятностей в узлах (рис. 1).

За счет требования d-разделимости (определение в главе приводится) байесовской сети доверия с корректной структурой сопоставляется единственное совместное (глобальное) распределение вероятностей, определенное на всех возможных означиваниях совокупности всех ее узлов, согласованное с условными и совместными (локальными) распределениями вероятностей в указанных узлах.

В ВСД связь глобального распределения с локальными выражается в виде цепного правила:

цепь

многосвязная структура

Допустимые структуры БСД (без направленных циклов) : х0 : '. Хо ; ', х,} { Хо ) ( J Хг ;

GD CD CD

р(УЫ Р(УЫ

Р(у1*Ь) p(7tr0)

CD

M

m

P№oXl ) P&lXoX,) pWWî) pWWlEl) p(y¡ToXlX¡) рШХЬ*|Х2)

Р№й) РСЙХО*,) р(у1Хо*Л) РОТХОХЛ) Р№>ХЛ) pCPpb*,rz)

РСЯВДО püWa) р(Л*оВД р(урда2) pOTWíxj)

P(y|Wi) РСЯW,) rtypísTO) pfflxMi) Р№оГЛ) PWWTi)

Условные и маргинальные вероятности в узлах БСД Рис. 1. Байесовские сети доверия.

Недопустимые структуры БСД (с направленными циклами)

в котором А — атомарные пропозициональные формулы (атомы), стоящие в узлах ВСД, литерал х £ {х,Я}, ра(х) — множество родителей х, а ра(х) — конъюнкция литералов, построенных над атомами из рэ(х). Означивания литералов в левой и правой части формулы должны совпадать.

Описаны алгоритмы двух видов логико-вероятностного вывода в ВСД: первичной пропагации (назначения априорной вероятности узлам сети исходя из имеющихся сведений о тензорах условных вероятностей) и пропагации свидетельства (распространение влияния свидетельства, поступившего в один или несколько узлов, на оценки вероятностей в других узлах). Указывается, что для обработки ВСД с допустимыми (ненаправленными) циклами (ВСД с многосвязной структурой) требуется ее преобразование в дерево сочленений. Процесс такого преобразования описав, приводятся формулировки теорем, характеризующих этот процесс. Отмечается, что хотя ВСД изучены заметно более широко, в них не допускаются интервальные оценки вероятностей и до сих пор не предложено подходов к обработке направленного цикла [7,15].

Глава 3 «ABC — логико-вероятностная графическая модель» содержит ряд релевантных объекту исследований определений и фактов из базовых теорий, а также формирует базовую систему определений объектов теории ABC, сопровождая ее необходимыми комментариями, связанными с вероятностной семантикой рассмотренных логико-вероятностных моделей фрагментов знаний, свидетельств и баз фрагментов знаний.

В главе приведены определения литерала х 6 {х,х}, образованного над атомом (атомарной пропозициональной формулой, пропозициональной переменной) х, случайного бинарного элемента X (СБЭ), связанного с литералом, случайной бинарной последовательности Я (СВП), связанной с конъюнкцией литералов. Введены также сокращенные записи для цепочки конъюнкций атомов, например X, и для цепочки конъюнкций литералов, например X.

На языке случайных бинарных последовательностей сформулированы понятия независимости, условной независимости, композиции распределений СБП и приведено доказательство теоремы о композиции распределений случайных бинарных последовательностей. Рассмотрение указанных вопросов существенно для

теории алгебраических байесовских сетей, поскольку вероятностная семантика как указанных сетей, так и их фрагментов — это распределение или семейство распределений случайной бинарной последовательности, образованной над атомами сети или фрагмента соответственно.

Введено определение вероятностного пространства (с упрощенной структурой по Н. Нильссону) над пропозициональными формулами, составленными над заданным алфавитом атомов. Сформулированы определения ряда особых видов пропозициональных формул. Пусть А = {хо, Х|,...,xn_i} — алфавит атомов.

Определение 3.1. Квант ■ • • 1 — цепочка конъюнкций всех атомов над заданным алфавитом {xq,X] , ...,xn_i}, причем атом входит либо сам, либо с отрицанием.

Определение 3.2. Набор квантов над алфавитом атомов А обозначим Q = Q(A)={xox,

Рассмотрим набор всех квантов Q как множество элементарных событий. Зададим на нем дискретную плотность вероятности р° : Q —> [0; 1], отвечающую следующим требованиям:

(Vq6Q)p°(q) > 0; (2)

Г = Т. (3)

q€Q

Введем вероятность р : 2^ —) [0;1], «распространив» традиционным образом плотность вероятности [18,20]: (VS С Q) p(S) = ]Г p°(q), и получим вероят-

qes

ностное пространство (Q,2^,p). Определим вероятностную меру на множестве пропозициональных формул 3" = 3~(Л), заданных над алфавитом А, следующим образом:

(Vf е ?} p(f) = p(S(f)), (4)

где S(f) — множество квантов, входящих в совершенную дизъюнктивную нормальную форму пропозициональной формулы f: f = \¡ q.

qsS(f))

Взяв за основу такое распространение вероятности на множество пропозициональных формул, мы получим новое вероятностное пространство: (Q,ÍF,р). Эта упрощенная структура вероятностного пространства по Н. Нильссону задает вероятность над всеми пропозициями, построенными над множеством атомарных формул из алфавита А.

Определение 3.3. Конъюнкт — это цепочка конъюнкций атомов из заданного алфавита.

Определение 3.4. Дизъюнкт — зттго цепочка дизъюнкций атомов из заданного алфавита.

Теорема 3.1. Пусть Ú = XZY, V = XZ, W = ZY, даны распределения вероятностей pi (V) над {V} и P2(W) над {W}, причем выполнены следующие условия: Set [X] П Set [Y] = 0, Set [X] Л Set [Z] = 0, Set [Y] П Set [Z¡ = 0 и VZ р, (Z) = p2(Z). Тогда

( 0, если pi (Z) = 0,

p(Ü) = p(XZY) = { P1 (XZ)p2ÍZY) - (5)

--¡г--, если pi (Z) О,

I Pi (Z)

является композицией распределений вероятностей pi (V) и p2(W).

Здесь под композицией понимается распределение, которое маргинализуется к исходным.

Математическая модель фрагмента знаний формализована как идеал конъюнктов со скалярными или интервальными оценками истинности (рис. 2). Альтернативные модели фрагментов знаний (фрагменты знаний с альтернативной струкутрой) определены над идеалом дизъюнктов и набором квантов, а также определен расширенный фрагмент знаний. Введена индексация квантов в наборе, конъюнктов и дизъюнктов — в соответствующих идеалах. За счет порядка, индуцированного индексацией, скалярные оценки вероятностей квантов, конъюнктов и дизъюнктов представлены в виде векторов С2'п', Р'п| и , а интервальные — в виде пар векторов, содержащих верхние и нижние границы оценок:

0)-.(п) и д+,(п)1 р-,(п) и р+,(п)( 0-,(п) и Е)+,(П)_ пуказывает на число атомов в алфавите, над которыми построены указанные множества пропозициональных формул; этот показатель опускают, если позволяет контекст.

Определение 3.5. Фрагмент знаний (ФЗ) со скалярными оценками — это пара вида {С,р}, где С — это идеал конъюнктов, а р — функция из С в интервал [0;1]. Фрагмент знаний будем обозначать е.

Определение 3.6. Фрагмент знаний с интервальными оценками — это структура вида (С, р), где С — идеал конъюнктов, ар — функция из С в множество интервалов вида {[а; Ь] : а, Ь 6 [0; 1 ], а < Ъ}.

Слова «математическая модель» опускаются; в диссертации под фрагментом знаний понимается, как правило, его вышеописанная математическая (более точно — логико-вероятностная) модель.

Определены три вида свидетельств (с указанием особенностей их обработки): детерминированное, стохастическое и неточное; два последних вида имеют общее название — недетерминированное свидетельство. Указанные три вида свидетельств представляются с помощью непротиворечивых фрагментов знаний с бинарными, скалярными и интервальными оценками соответственно. Особенность недетерминированных свидетельств состоит, помимо прочего, в том, что они могут иметь зависимые компоненты.

Введены понятия графа смежности и его подвидов: дерева смежности, цепи смежности, цикла смежности. Представлены методы построения графа смежности по набору его вершин с заданными весами.

Определение 3.7. Граф смежности — это ненаправленный граф, в котором:

1) между каждой парой узлов, веса которых содержат общие элементы, существует путь; 2) в веса каждого из узлов пути, указанного в предыдущем пункте, входят все элементы, общие для начального и конечного узлов; 3) вес одного узла графа не входит полностью в вес никакого другого узла.

Определение 3.8. Определим алгебраическую байесовскую сеть 74 как набор фрагментов знаний: !№ = , или в случае скалярных оце-

нок - 7г> ={(^,^,»5:7.

Определение 3.9. Носителем N = зирр (ЗчГ) алгебраической байесовской сети >Г будет объединение идеалов конъюнктов, лежащих в основе фрагментов знаний, 1=п

вошедших в сегоъ: N — у .

1=1

Определение 3.10. Вторичная структура алгебраической байесовской сети — это граф смежности, узлы которого находятся во взаимнооднозначном соответствии с фрагментами знаний, вошедших в первичную структуру сети, при-

Р(*г) Р(хл)

xixzxix^

ХЛХз

№ Аъ)

Р(*1«г)

Р(*з>

Р(*Л)

р(х,хгх3)

М РМ РМ

Р(*з)

Р(*<Х3)

Р(*г*5)

Р(*1*ЗХЭ>

Р(*<)

Р(»1*4)

Р(*Л) Р^хл)

р(Х1Х2Х)Х<)

<Х1, Х;, Х3, х4>

Фрагменты знаний АБС

<Х1Х2> I-<*1=-1 <*1Х3>

<Х1Х;Хз> Н*зН <ХзХ«Х5> К<¿5*4 <Х5Хб>

| <Х,Х2> И*Н <Х,Х5>

I

<Х4Х5> I

<Х3>_<Х4>"

I <ХзХ4>~Т

Циклы (как вариант графа смежности)

<Х1Х;Х^>1-<ХгХ4>-Г<ХгХ4Х5> |—<х5>—| <ХдХв>~

I <Х1Х2> Ь<*»4 <Х?Х3> [<ХД>-.....<Х|И>-[ <ХП-1ХП>

I <Х1Х2Хз> |-<х,х,>-| <ХгХзХ^~1-<х^хмН <Х^Х„,Х„> "1 1 <х.х;> К>) <хгх3>

Цепи смежности

сз-сгк.

х*

<х2Хз> Ихэ>] <ХЛ>

--осэ -Чгмш

Дерево смежности

Граф смежности с циклом

Рис. 2. Фрагменты знаний и алгебраические байесовские сети с различной структурой.

■чем весом узла является идеал конъюнктов (без пустого элемента), являющийся носителем соответствующего фрагмента знаний (рис. 2).

В диссертации рассматриваются алгебраические байесовские сети только с заданной связной вторичной структурой. Если ABC распадается на несколько компонент связности, то эти компоненты считаются независимыми и обрабатываются по отдельности. Алгебраическая байесовская сеть, вторичная структура которой представлена в виде дерева смежности, называется ациклической (ААВС).

В отношении конечной совокупности фрагментов знааий и конечной совокупности алгебраических байесовских сетей одинаковой структуры определены операции линейной комбинации и линейной оболочки.

Вероятностной семантикой фрагмента знаний со скалярными оценками вероятностей считается распределение вероятностей, члены которого удовлетворяют указанным оценкам, если такое распределение существует. Вероятностной семантикой фрагмента знаний с непротиворечивыми интервальными оценками является семейство распределений вероятностей, члены которого удовлетворяют указанным оценкам. Если оценки на фрагменте знаний противоречивы (несовместны), то считается, что такой ФЗ задает пустое семейство распределений.

Вероятностной семантикой алгебраической байесовской сети является семейство распределений вероятностей, определенных над квантами, построенными над всеми атомами, вошедшими в сеть, причем каждое распределение удовлетворяет оценкам, которые заданы в сети. Такое семейство может оказаться пустым, если набор исходных оценок окажется противоречивым (несовместным). В ациклических ABC со скалярными оценками, предъявляя особым образом сформулированное требование условной независимости, из семейства распределений удается выделить одно распределение вероятностей.

Глава 4 «Локальный логико-вероятностный вывод» содержит обоснование ма-трично-векторных уравнений, связывающих оценки вероятностей элементов фрагментов знаний с дискретной плотностью вероятности на соответствующем конечном вероятностном пространстве и таким образом формализующих вероятностную семантику указанных фрагментов; описание и методы решения задач различных видов локального логико-вероятностного вывода: проверки и поддержания непротиворечивости ФЗ (в том числе альтернативной структуры), априорного вывода в ФЗ, апостериорного вывода в ФЗ при поступлении детерминированного, стохастического и неточного свидетельств; различные характеристики результатов локального логико-вероятностного вывода, а также заключение о том, что непротиворечивость ФЗ сохраняется относительно операций линейной комбинации и линейной оболочки; наконец, обоснование единственности минимального (по включению интервалов оценок) результата локальной операции «накрывающей» непротиворечивости при непротиворечивых исходных данных. Кроме того, в главе приводится ряд примеров, иллюстрирующих основные понятия и операции. Заметим, что поддержание непротиворечивости и априорный вывод в силу сходства используемых принципов объединяются под общим названием синтез согласованных оценок истинности.

Определение 4.11. Пусть из алфавита атомов выбрано подмножество S, над которым построен идеал конъюнктов С = C(S), над которым, в свою очередь, построен фрагмент знаний со скалярными оценками вероятностей С = (С,рд). Кроме того, определено соответствующее множество квантов Q = Q(S). Фрагмент знаний е (со скалярными оценками рл) непротиворечив тогда и только тогда, когда существует такая дискретная плотность вероятности на квантах Q: р° : Q —> [0;1], которая удовлетворяет требованиям, вытекающим из аксиоматики вероятностей, и индуцирует вероятность р на

пропозициональных формулах 3"(S), сужение которой на конъюнкты совпадает с рл,- (Vfe с) pA(f)=P(f).

Определен предикат Consistent [С], который истинен тогда и только тогда, когда его аргумевт-ФЗ со скалярными оценками С непротиворечив. Аргумент предиката допускает альтернативные записи, «раскрывающие» обозначение С.

Определение 4.12. Пусть из алфавита атомов выбрано подмножество S, над которым построен идеал конъюнктов С = C(S), над которым, в свою очередь, построен фрагмент знаний с интервальными оценками вероятностей 6 = (С, рЛ). Фрагмент знаний е (с интервальными оценками рл) непротиворечив тогда и только тогда, когда выполнено следующее условие:

Vf е С Vp

ЭрЛ 6 {ср

Определен также предикат Consistent [С] для случая интервальных оценок.

Определение 4.13. ФЗ (С,рд) с интервальными оценками является согласуемым, если существует такой непротиворечивый набор скалярных оценок р', что (Vf £ e)p'(f) 6 PA(f).

Определен ряд матриц и векторов (вектор-столбцов):

*-(г ?)• М? !)• "О- О-

а также их степени Кронекера (прямые степени):

т _ т'т' ч _-»It-n-î ^ _p[ml ç г»

1т — А] > )т — < . Cm — c-i I c.m — е., , wm — ,

1 _-i Гт.] - _ -.[т.] X _ , _ 0[ml

' m — ' ) I I'm — > um — Ui i Vm — V}

Исследованы свойств^ матриц Im и Jm; в частности, показано, что они являются взаимнообратными.

Теорема 4.2.

Imp(™i = Q(m> (6)

JmQ(m)=P(m) (7)

Пояснение. Линейные матрично-вектрные уравнения (6) и (7) выражают вероятности квантов Q'm' через вероятности конъюнктов и наоборот.

Предложение 4.1. Требования аксиоматики вероятностной логики (2-3) к значениям дискретной плотности вероятностей на квантах в матрично-век-торном виде выразятся как

Qlm) > 0т, (8)

Q(m)1m = 1. (9)

€ PA(f)

I <р : С —> [0;!]} : (pA(f) = p)& & (V9eC:pA(g)6pA(g))& & Consistent [(С,рл)1 .

Рис. 3. Матрицы 13 и I4. Здесь вертикальная штриховка означает плюс одкя, горизонтальная — минус один, а неэаштрихованные области считаются заполненными нулями.

Теорема 4.3. Для того чтобы, фрагмент знаний С = (С,Р'т') со скалярными оценками вероятностей был непротиворечивым, необходимо и достаточно, чтобы выполнялось векторное неравенство

ImP(ml > От. (10)

Для задачи проверки непротиворечивости фрагмента знаний алгебраической байесовской сети, построенного над идеалом конъюнктов со скалярными оценками, теорема 4.3 обеспечила метод решения: вектор оценок достаточно подставить в векторное неравенство (10) и проверить справедливость последнего. Примеры структуры матриц Im приведены на рис. 3.

Теорема 4.4. Линейная комбинация конечного числа обладающих одинаковой структурой непротиворечивых фрагментов знаний со скалярными оценками непротиворечива.

Определение 4.14. £'т' — множество линейных ограничений, состоящее из линейных неравенств, задаваемых условием «неотрицательности» (]0).

Определение 4.15. — множество линейных ограничений на основе све-

дений из предметной области, состоящее из двойных линейных неравенств над вероятностями элементов идеала и представимое в векторном виде как р-,(т) < р(т) ^ где — вектор, составленный из констант —

(исходных) нижних границ вероятностей соответствующих конъюнктов, а р+,(т) _ такод мсе вектор, но содержащий верхние границы. Компоненты обоих векторов с нулевым индексом всегда равны единице.

Роль переменных в указанных системах ограничений £'т' и D'm' играют компоненты вектора р'т'; кроме того = £>(m) и £(т'. Заметим, что для

удобства показатель (т) можно опускать.

Определение 4.16. Векторы уточненных нижних и верхних оценок вероятностей обозначаются u p+.tm.) соответственно.

Если опустить показатель (та), задачи линейного программирования в векторных обозначениях запишутся таким образом:

P~=min{P), Р+ =ш_ах{Р}, (11)

где поиск минимума и максимума осуществляется почленно и независимо.

Теорема 4.5. Фрагмент знаний С = {С.Рд.Р^) является согласуемым тогда и только тогда, когда имеет решение хотя бы одна задача линейного программирования из (1 1).

Замечание 4.1. Если хотя бы одна задача линейного программирования из (11) имеет решение, то все остальные задачи из (11) будут иметь решение.

Замечание 4.2. Если хотя бы одна задача линейного программирования из (11) не имеет решения, то все остальные задачи из (11) не имеют решения.

Теорема 4.6. Если задачи линейного программирования из (11) имеют решения, то фрагмент знаний С = (С, Р~,Р+)с [возможно] уточненными интервальными оценками непротиворечив, а оценки представляют собой замкнутые промежутки.

Следствие 4.1. При повторной попытке уточнить оценки с помощью решения серии задач линейного программирования в непротиворечивом фрагменте знаний из теоремы 4.6 имеющиеся оценки не уточнятся (не сузятся).

Приведена схема одного из возможных алгоритмов, реализующих предложенный выше метод проверки и поддержания непротиворечивости фрагмента знаний.

Теорема 4.7. Линейная комбинация конечного числа обладающих одинаковой структурой непротиворечивых фрагментов знаний с интервальными оценками непротиворечива.

Теорема 4.8. Линейная оболочка конечного числа обладающих одинаковой структурой непротиворечивых фрагментов знаний с интервальными оценками непротиворечива.

Определение 4.17. Пусть задан упорядоченный набор из п фрагментов знаний одинаковой структуры (т.е. построенных над одинаковым идеалом конъюнктов С) с интервальными оценкалш (С^ = . Тогда семейство С постро-

енных над тем же идеалом конъюнктов непротиворечивых фрагментов знаний вида С = (С,р) с интервальными оценками является результатом операции <гнакрывающей» непротиворечивости фрагментов знаний из исходного набора е = Сог^егПЕпсЬзиге [(еи^""1] , если 6 С) (VI : 0 < г < (п- 1)) р1{Я С Р (Я

Теорема 4.9. Пусть задан упорядоченный набор из тг непротиворечивых фрагментов знаний одинаковой структуры (т.е. построенных над одинаковым идеалом конъюнктов С) с интервальными оценками = . Тогда наименьшим по включению элементом семейства непротиворечивых фрагментов знаний, сформированным в результате операции <гнакрывающей» непротиворечивости фрагментов знаний из исходного набора, является линейная оболочка

1=П-1

Щ С; последнего. 1=0

В диссертации доказаны аналогичные теоремы относительно непротиворечивых фрагментов знаний альтернативной структуры и операций линейной комбинации, линейной оболочки и «накрывающей» непротиворечивости. Методы проверки и поддержания непротиворечивости основываются на следующих матрично-векторных уравнениях и неравенствах. Для фрагмента знаний (Зд = {Су, И) задание скалярных оценок считается непротиворечивым, если ГО ^ 0- Для фрагмента

знаний Sq = (Q, Q) задание скалярных оценок считается непротиворечивым, если Q > О и Q1 = 1.

Заметим, что вероятность любой пропозициональной формулы f из F(A) выражается как сумма вероятностей некоторых квантов из Q(A). Вероятности же квантов линейно выражаются через вероятности конъюнктов. Следовательно, вероятность f линейно выражается через вероятности конъюнктов:

(VfeF(A)) Э! Llml : p(f) = Ltm)Plm), (12)

где L'"1' — вектор вещественных хонстант, совпадающий по размерности с Р'т'. Вели требуется оценить вероятность формулы f, опираясь на оценки вероятностей элементов идеала конъюнктов, то пополнив множество 3i'm) уравнением p(f) = I_(m)p(m) и решив здп по минимизации и максимизации переменной p(f), мы получим искомую оценку. Если же требуется учесть наше знание об интервальной оценке величины p(f), то подобным же образом множество пополняется

ограничением (12) и ограничением, исходящим из предметной области: рй (f) ^

Определение 4.18. Локальный априорный вывод заключается в том, чтобы по известным оценкам вероятности истинности заданных во фрагменте знаний пропозициональных формул построить оценку вероятности истинности пропозициональной формулы, не вошедшей в число заданных.

Пояснение. Локальный априорный вывод можно трактовать более широко: пропозициональная формула может входить во фрагмент знаний, но оценка вероятности ее истинности неизвестна (т.е. представлена интервалом [Ojl]^. Поиск оценки вероятности истинности такой пропозициональной формулы тоже можно включить в состав задачи локального априорного вывода.

Рассмотрено построение (или уточнение) оценок ФЗ на основе оценок произвольного набора пропозиций над заданным алфавитом, которое происходит аналогично процессу поддержания непротиворечивости, только к набору ограничений Ви£ добавляются ограничения вида pjT < LfP < pf, где pjT ир+ — нижняя и верхняя оценки вероятности формулы f. В общем случае к оценкам фрагмента знаний могут быть добавлены произвольные оценки (в виде равенств или нестрогих неравенств) линейных форм, построенных над вероятностями элементов ФЗ. В этой ситуации мы говорим о расширенном фрагменте знаний. Заметим, что вероятности пропозиционалдьных формул, построенных над теми же атомами, что и элементы ФЗ, представимы в виде указанных выше линейных форм.

Таким образом, численные (т.н. количественные) ограничения на вероятности элементов ФЗ или расширенного ФЗ могут либо отсутствовать и заменяться т.н. качественными оценками (т.е. линейными равенствами и нестрогими неравенствами с участием линейных форм над вероятностями элементов ФЗ), либо дополняться последними. После процесса поддержания непротиворечивости в таком расширенном ФЗ либо его элементы получат уточненные количественные оценки, либо обнаружится противоречивость исходных данных.

Выбраны метрики r(P,P) — max — ptl и d{0,р) = — р|. Процесс

О <i.<(2TV — 11

оценивания чувствительности результата локального априорного вывода в случае скалярных исходных данных сводится к решению набора ЗЛП:

е= max №-р,р-£}, е(Р0) = „ max {£-p,p-fl}.

r(f,P)<4, r(f>,P)<6, P=P„

p=tP,£=L{>

2n-l

Теорема 4.10. Справедливо неравенство d(f),p) < 6 £ IUIi где к — коэффи-

i= 1

циенты в разложении вероятности тр пропозициональной формулы на вероятности конъюнктов, а 6 — радиус вариации: r(P, Р) ^ 6.

Указанное неравенство характеризует верхнюю оценку чувствительности априорного вывода в случае скалярных исходных данных.

В качестве развернутого примера в тексте диссертации синтез согласованных оценок истинности применен в задачах локального машинного обучения алгебраических байесовских сетей [20].

Первой задачей апостериорного вывода является оценка вероятности или ожидаемой вероятности появления свидетельства {()) над заданным ФЗ е или заданной ВФЗ Nkpb: р((())|С) и соответственно p((())|Wkpb )•

Второй задачей апостериорного вывода является оценка апостериорной вероятности или ожидаемой апостериорной вероятности конъюнктов Zy, входящих в ФЗ или ВФЗ, но не имеющих общих атомов с поступившим свидетельством: PatZvl«)»-

В главе отдельно рассмотрена ситуация, когда поступает свидетельство, имеющее нулевую вероятность реализации над ФЗ. Оценки апостериорных вероятностей соответствующих элементов в этом случае приравниваются [0; 1].

Детерминированное свидетельство задается конъюнкцией над частью атомов из ФЗ, причем в эту конъюнкцию входит либо сам атом, либо его отрицание. Детерминированное свидетельство в общем случае обозначается (X), причем подразумевается, что X принимает конкретное означивание, соответствующее свидетельству. Используя индексацию, такое свидетельство можно представить как (с{, Cj), где с^ и Cj — конъюнкты, состоящие из атомов, получивших положительные и отрицательные означивания соответственно. Для краткости также используется обозначение (i, j), где i и j — индексы соответствующих конъюнктов.

Стохастическое свидетельство задается в виде непротиворечивого ФЗ со скалярными оценками над частью атомов из исходного ФЗ и в общем случае обозначается (Р[а](Х)}, где р[а] задает апостериорное распределение вероятностей в свидетельстве.

Неточное свидетельство задается в виде непротиворечивого ФЗ с интервальными оценками над частью атомов из исходного ФЗ и в общем случае обозначается (P[a) (X) £ Рг[а][Х]), где Рг[а] задает семейство апостериорных распределений вероятностей в свидетельстве.

После рассмотрения постановки задач локального апостериорного вывода в случае различных сочетаний исходных данных сделан вывод, что ключевым методом выступает метод обработки детерминированного свидетельства, а методы обработки стохастического и неточного свидетельств осуществляются на его основе. Например, в случае скалярных оценок в ФЗ решением второй задачи апостериорного вывода при стохастическом свидетельстве является

(ZYl<P[a] (Х)> ) = £ Pa (ZY|(X»P[a] (*).

X

Для удобной при вычислениях и анализе результатов формализации методов локального апостериорного вывода осуществлен переход к постановке возникающих задач на матрично-векторном языке.

*-«•-(;?), н--('•); н-(;;).

Определим Н<4'>> = Н^, ® Н^ ® ... , где

- (1 ) > I ' еслк кк входит в С;; Нк ' = < Н-, если Хк входит в с,; ( Н°, иначе;

Т(М> =

Тогда вероятность детерминированного свидетельства над фрагментом знаний со скалярными оценками С = (С, Р) вычисляется как

Р«съ^)|е) = (Т<1-'> Р)[0]. (13)

На основе формулы (13) можно построить вектор -СЛ1-'), соответствующий первой строке матрицы такой, что

р((с1,с))|е) = с<1-»р. (14)

Теорема 4.11. Если р((сг,с)}|6) ^ 0, то формула (15) дает решение второй за-¿)ачи апостерионого вывода в случае детерминированного свидетельства и скалярных оценок в ФЗ С = (С, Р);

р<М> =_!_т<'Ч>Р= ^^ (15)

(Т<1;)>Р)[01 (Т<г;,>Р)[0)

Теорема 4.12. Решением второй задачи локального апостериорного вывода е случае детерминированного свидетельства и интервальных оценок истинности во фрагменте знаний является решение серии задач линейного программирования по поиску:

р(ь)> - =шш{ТМ>0) и р<*.)),+ =тах{Т<1;'>0} (16)

при условиях: {ЛР~ < О} и {О < АР+}и {Ш ^ 0}и{Л.<г''>0 = 1}и{Л> 0}.

Минимумы и максимумы от Р''1'^ = берутся почленно и независимо.

Теорема 4.13. В обозначениях теоремы, 4.12 фрагмент знаний с апостериорными оценками вероятностей

(С,р(1.!>.-,р<1.)>.+ ) непротиворечив, если задачи линейного программирования (Тб) имеют решение.

Следствие 4.1. Из справедливости теоремы 4.13 следует, что результаты локального апостериорного вывода по стохастическому и неточному свидетельству также будут непротиворечивыми, если исходные данные были непротиворечивы и соответствующие ЗЛП имели решение.

Методы обработки стохастического и нечеткого свидетельства также формализованы с помощью матрично-векторного языка.

Решена задача по анализу чувствительности в отношении ненормированного результата апостериорного вывода в случае скалярных априорных оценок и детерминированного свидетельства. Обозначим соответствующие объекты как Ра (с), ■ра< (с), и Ра . Тогда целевые функции будут выглядеть как

Оа ', Р°') = ЦТ<'Л> [Ра> - Ра' )|| < ||Т<1'»|| ■ 11(Ра' - Ра')11,

¿а (Г'(с)>Рп'(с)) =(|Т<и>(К -Ра')||<||Т<1'П|Н1(К-Ра')!1.

При надлежащем подборе метрик Оа и <1а (как и в априорном выводе) полученные формулы позволяют использовать задачи линейного программирования в оценке чувствительности ненормированного результата апостериорного вывода.

Глава 5 «Логико-вероятностный вывод в ациклической АБС» содержит описание методов решения двух задач, в которых требуется 1) проверить и поддержать непротиворечивость сети, т.е. убедиться, что ее вероятностная семантика «непуста» (исходные оценки совместны) и, по возможности, уточнить эти оценки; 2) распространить влияние свидетельства, поступившего в один из фрагментов знаний ациклической АБС. Кроме того, предложен метод преобразования ациклической байесовской сети доверия со случайными бинарными элементами в узлах в ациклическую АБС с сохранением вероятностной семантики.

Определение 5.19. АБС считается локально непротиворечивой, если каждый отдельно взятый фрагмент знаний з сети непротиворечив:

(Vee^i0) Consistent [С].

Определение 5.20. АБС считается экстернально непротиворечивой, если каждый фрагмент знаний в сети непротиворечив

(ve е :№) Consistent [е],

а также оценки истинности любого конъюнкта, входящего одновременно в два фрагмента знаний или более, совпадают:

(ve' б зч"0) (ve" e №) (vf e c'nc") P'(f) = p"{f).

Определение 5.21. АБС считается интернально непротиворечивой, если каждый фрагмент знаний е сети непротиворечив, а также для любого конъюнкта из АБС для любого скалярного значения из интервала оценки его истинности можно выбрать согласованные (т.е. совпадающие на одинаковых формулах) скалярные значения во всех фрагментах знаний так, что все получившиеся ФЗ со скалярными оценками будут непротиворечивы:

(Vf 6 N) (Vp 6 p(f)) (Эр' : N —> [0;1])

p'(f) = p&(Ve 6 У!0) Consistent [(C,p'|c)] •

Определение 5.22. АБС считается глобально непротиворечивой, если ее с имеющимися оценками можно погрузить в непротиворечивый объемлющий фрагмент знаний G и при этом оценки рм (f) на конъюнктах из АБС не изменятся:

(Зе = (C,pc))Consistent[e] & N С С & (Vf 6 N)pc(f) = Pn (f)-

Бероятностной семантикой алгебраической байесовской сети является семейство распределений вероятностей, определенных над квантами, построенными над всеми атомами, вошедшими в сеть, причем каждое распределение удовлетворяет оценкам, которые заданы в сети. Такое семейство может оказаться пустым, В ациклических ABC, предъявляя особым образом сформулированное требование условной независимости, из семейства распределений удается выделить одно распределение вероятностей.

Каждая последующая степень непротиворечивости не слабее предыдущей. Основной смысл введения различных степеней непротиворечивости заключается в том, что вычислительная сложность их проверки увеличивается от первой к последней. Метод поддержания глобальной непротиворечивости АБС полностью соответствует методу поддержания непротиворечивости объемлющего ФЗ; разработан метод поддержания интернальной непротиворечивости АБС.

В главе получен ряд дополнительных результатов относительно операции композиции распределений случайных бинарных последовательностей, который создает основу как для анализа отношений между степенями непротиворечивости, так и для анализа особенностей глобального апостериорного вывода.

Теорема 5.14. Пусть АБС является ациклической, тогда из ее интерналъной непротиворечивости следует ее глобальная непротиворечивость.

Теорема 5.15. 1) Алгебраическая байесовская сеть, непротиворечивая глобально, является непротиворечивой интернально; 2) алгебраическая байесовская сеть, непротиворечивая интернально, является непротиворечивой экстерналъно; 3) алгебраическая байесовская сеть, непротиворечивая экстерналъно, является непротиворечивой локально.

«Движение» в обратную сторону по цепи степеней непротиворечивости в общем случае невозможно, как это было показано с помощью контрпримеров: в общем случае 1) из локальной непротиворечивости ABC не следует ее экстер-нальная непротиворечивость, 2) из экстернальной — интернальная, 3) а из интерналъной — глобальная.

Теорема 5.16. Экстернально непротиворечивая АБС со скалярными оценками является интернально непротиворечивой.

Теорема 5.17. Экстернально непротиворечивая ациклическая АБС со скалярными оценками является интернально непротиворечивой, а значит, и глобально непротиворечивой.

Теорема 5.18. Экстерналъно непротиворечивая ациклическая АБС, фрагменты знаний которой попарно имеют не более одного общего атома, является интернально непротиворечивой, а значит, и глобально непротиворечивой.

Теорема 5.19. Пусть дан конечный набор алгебраических байесовских сетей одинаковой структуры и одинаковой степени непротиворечивости. Линейная комбинация этого набора будет непротиворечива в той otee степени.

Теорема 5.20. Пусть дан конечный набор алгебраических байесовских сетей одинаковой структуры и одинаковой степени непротиворечивости. Линейная оболочка этого набора будет непротиворечива в той же степени.

Теорема 5.21. Пусть задан упорядоченный набор (Nil^J)-1 из и алгебраических байесовских сетей одинаковой структуры (то есть, построенных над одинаковым носителем N) с интервальными оценками Pi(f) для элементов сети 0 < i < (rv —' 1), и одинаковой степени непротиворечивости. Тогда наименьшим по включению элементом семейства непротиворечивых алгебраических байесовских сетей, сформированным в результате операции «•накрывающей» непротиворечивости указанной степени алгебраических байесовских се-

i=ri-l

тей из исходного набора, является линейная оболочка JVt последнего.

1=0

Теорема 5.22. Алгоритм поддержания глобальной непротиворечивости АБС завершает работу и имеет на выходе один из двух результатов: непротиворечивые оценки вероятностей элементов данной ABC или сообщение о противоречивости исходных оценок вероятностей элементов данной АБС.

Теорема 5.23. Алгоритм поддержания интерналъной непротиворечивости АБС завершает работу и имеет на выходе один из двух результатов: непротиворечивые оценки вероятностей элементов данной АБС или сообщение о противоречивости исходных оценок вероятностей элементов данной АБС.

Теорема 5.24. Оценки вероятностей элементов АБС, полученные в результате применения алгоритма поддержания глобальной непротиворечивости, являются непустъши замкнутыми промежуткалш.

Теорема 5.25. Оценки вероятностей элементов АБС, полученные в результате применения алгоритма поддержания интерналъной непротиворечивости, являются непустыми замкнутыми промежутками.

Вычислительная сложность алгоритмов, реализующих предложенные методы проверки интернальной и глобальной непротиворечивости, характеризуется указанием числа переменных и ограничений в задачах линейного программирования, требующих решения, а также собственно числом таких задач. При построении указанных оценок следует учитывать, что по предположению, лежащему в основе теории алгебраических байесовских сетей, фрагменты знаний имеют ограниченный размер. Они могут быть построены над 2-3-4 атомами. (Чуть более обще — число атомов, над которыми построен ФЗ, ограничено и является небольшим.)

Предложение 5.2. Пусть АБС построена над алфавитом из п атомов и состоит из к фрагментов знаний, каждый из которых построен не более, чем над г атомами. Тогда для проверки глобальной непротиворечивости такой АБС потребуется решить задачу линейного программирования с 2"- — 1 переменными, 2п ограничениями, вытекающими из требований аксиоматики вероятностной логики, и не более, чем 2к(2г — 1) ограничениями из предметной области. Для поддержания глобальной непротиворечивости такой АБС потребуется решить не более, чем 2k(2r — 1) задач линейного программирования с указанным множеством ограничений.

Предложение 5.3. Пусть АБС построена над алфавитом из п атомов и состоит из к фрагментов знаний, каждый из которых построек не более, чем над г атомами. Тогда для проверки интернальной непротиворечивости такой АБС потребуется решить задачу линейного программирования с не более, чем О(к) = к(2г — 1) переменными, О(к) = к(2г) ограничениями, вытекающими из требований аксиоматики вероятностной логики, и не более, чем 2к(2г —1) ограничениями из предметной области. Для поддержания интернальной непротиворечивости такой АБС потребуется решить не более, чем 2к(2г — 1) задач линейного программирования с указанным множеством ограничений.

Пояснение. Именно этот факт показывает важность понятия (состояния) интерналъной непротиворечивости в случае ациклических алгебраических байесовских сетей: вместо экспоненциальных по числу переменных и ограничений задач линейного программирования достаточно решить задачи линейного программирования, число переменных и ограничений в которых линейно зависит от числа ФЗ.

Пусть в узел дерева смежности (т.е. во фрагмент знаний) поступило свидетельство. Наша задача состоит в том, чтобы распространить его влияние на каждый ФЗ, входящий в ABC, представленную в виде дерева смежности. Метод решения задачи основан на ее сведении к уже известным операциям над более простыми объектами.

Между узлом, в который поступило свидетельство, и любым другим узлом существует путь (без самопересечений!), поскольку мы рассматриваем только связные графы. Этот путь единственный. Требуется распространить свидетельство «вдоль» этого пути. Сведем далее задачу к распространению свидетельства из некоторого выбранного узла в соседний.

Напомним, что любое свидетельство можно представить в виде фрагмента знаний. Пусть свидетельство поступило в первый узел. Это вызовет перерасчет вероятностей всех элементов фрагмента знаний, стоящего в этом узле, причем на элементах, общих со свидетельством, сформируются апостериорные оценки вероятностей, совпадающие с теми, которые были в свидетельстве [18].

Рис. 4. Распространение влияния стохастического свидетельства в случае скалярных оценок вероятностей.

Рассмотрим пересечение первого и второго фрагментов знаний. Оно строится над идеалом конъюнктов и может быть рассмотрено как фрагмент званий, который является подфрагментом двух исходных. Обработаем этот подфрагмент знаний с новыми (апостериорными) оценками вероятностей как виртуальное свидетельство, исходящее из первого фрагмента знаний и поступающее во второй — таким образом влияние исходного свидетельства распространится через промежуточное виртуальное свидетельство на второй фрагмент знаний.

Пусть задана глобально непротиворечивая ациклическая ABC, то есть, пред-ставимая в виде дерева смежности. Оценки вероятностей элементов в АБС скалярные. Пусть также в один из фрагментов знаний на вход поступает стохастическое свидетельство. Метод распространения свидетельства от фрагмента знаний к фрагменту знаний проиллюстрирован на рис. 4.

Расчеты ведутся по формулам, основанным на уравнении (15).

Теорема 5.26. Пусть задана непротиворечивая ациклическая алгебраическая байесовская сеть X со скалярными оценками вероятностей истинности своих элементов и объемлющий ее фрагмент знаний С. На ФЗ С распределение вероятностей получено последовательным применением операции композиции к распределениям вероятностей над фрагментами знаний из АБС Ъ!. Тогда распространение влияния стохастического свидетельства, поступающего в один из фрагментов знаний исходной АБС, даст одинаковые результаты как через распространение виртуальных свидетельств в сети так и при распространении влияния стохастического свидетельства в ФЗ С.

Предложение 5.4. Метод распространения виртуальных свидетельств для обработки стохастического свидетельства, поступившего в ациклическую алгебраическую байесовскую сеть со скалярными оценками, потребует О(к) операций сложения, умножения и деления, где к — число фрагментов знаний в сети. Метод погружения АБС в объемлющий ФЗ для обработки стохастического свидетельства, поступившего в ациклическую алгебраическую байесовскую сеть, потребует 0(exp(d)) операций сложения, умножения и деления, где d — число атомов в сети.

Теорема 5.27. Любая ациклическая байесовская сеть доверия с бинарными случайными элементами в узлах может быть преобразована в ациклическую АБС, фрагменты знаний которой имеют в пересечении не более одного атома.

В диссертации описав метод такого преобразования. Этот метод непосредственно обобщается на ациклические ВСД, в узлах которых стоят попарно непересекающиеся СВП.

Глава 6 «Циклы в байесовских сетях» посвящена методам преобразования и обработки цикла смежности фрагментов знаний в ABC (цикла фрагментов знаний АБС, цикла ФЗ ABC) и направленного ВСД-цикла (ВСД-цикла).

Определение 6.23. Цикл смежности фрагментов знаний (ЦФЗ) АБС — это алгебраическая байесовская сеть со вторичной структурой, представленной в виде графа смежности, являющегося циклом.

Алгоритмы логико-вероятностного вывода, разработанные для ациклических алгебраических байесовских сетей, не применимы непосредственно к циклам фрагментов знаний, которые допустимы в ABC в общем случае. Погружение такого цикла в объемлющий фрагмент знаний формально открывает возможность для применения известных схем алгоритмов локального вывода, но имеет экспоненциальную сложность с точки зрения используемого объема данных: возникающие задачи линейного программирования будут иметь экспоненциально растущее число перемгнных и ограничений отнссительво роста числа атомарных пропозиций, входящих в исходный цикл.

Предложен метод преобразования на основе погружения пар фрагментов знаний в объемлющие ¡фрагменты знаний] цикла смежности фрагментов знаний ABC в цепь смежности фрагментов знаний ABC за счет построения новых фрагментов знаний над специальным образом сформированными парами исходных фрагментов знаний и, особо, либо над еще одним исходным фрагментом знаний, либо над тройкой исходных. Указанное преобразование можно выполнить разными способами.

Теорема 6.28. Для того чтобы цикл фрагментов знаний в АБС был глобально непротиворечив, необходимо и достаточно, чтобы цепь смежности фрагментов знаний, полученная из указанного цикла за счет преобразования на основе погружения пар фрагментов знаний в объемлющие, была глобально непротиворечива.

Теорема 6.29. Для того чтобы цикл фрагментов знаний в АБС был глобально непротиворечив, необходимо а достаточно, чтобы цепь смежности фрагментов знаний, полученная из указанного цикла за счет преобразования на основе погружения пар фрагментов знаний в объемлющие, была интернально непротиворечива.

Предложение 6.5. В задаче линейного программирования, решаемой для проверки непротиворечивости цикла смежности фрагментов знаний АБС, число ограничений, исходящих из аксиоматики вероятностной логики, и число переменных в задаче линейного программирования имеют порядок не выше, чем О(п) в случае преобразования цикла в цепь смежности, а при погружении цикла в объемлющий фрагмент знаний указанные числа растут экспоненциально с ростом п, где п — число атомов в алфавите, над которым построен цикл.

Для частных случаев циклов предложены уточненные оценки.

Теорема 6.30. Пусть в цикле фрагментов знаний алгебраической байесовской сети присутствуют два одинаковых сепаратора,

то есть А'1" = А'1'' ' = А'. Тогда хотя бы в одном из двух путей, состоящих из фрагментов знаний, оказавшихся между этими двумя сепараторами, все сепараторы и все фрагменты знаний построены над множествами атомов, содержащих А'. Более того, такие сепараторы и фрагменты знаний содержат в качестве подыдеала идеал вида (А').

По определению индексы г и j, а также i' и j' ссылаются на пары смежных фрагментов знаний соответственно.

На основе теоремы 6.30 предложен метод, позволяющий «сократить» цикл за счет выделения из него цепи смежности фрагментов знаний.

Определение 6.24. Направленный БСД-цикл — это направленный граф, являющийся направленным циклом, в котором каждому узлу приписан случайный бинарный элемент, вероятность конкретного означивания которого с помощью тензора условных вероятностей, также приписанного указанному узлу, определяется означиванием случайного бинарного элемента в узле-родителе.

Для обработки направленного ВСД-цикла предложен метод формирования его образа в виде цикла фрагментов знаний АБС, эквивалентного с точки зрения вероятностной семантики исходному БСД-циклу; этот образ затем преобразуется в цепь смежности ФЗ АБС. Конечный результат преобразований можно обработать известными для ациклических АБС алгоритмами логико-вероятностного вывода.

Указанный метод [19] основывается на переходе от тензоров условных вероятностей, приписанных узлам направленного БСД-цикла, вида p(xi|xj) к набору маргинальных вероятностей атомов p(xt), стоящих в узлах цикла, и конъюнкций пар атомов p(xjxt) из смежных узлов цикла. Определено: хо = х^, где к — число атомов в цикле, и индекс j непосредственно предшествует индексу i.

Пусть неизвестная р(хо) = tí. Последовательно используя формулу полной вероятности, получим p(x¡J = pi(7t); тогда tí определяется из уравнения

тг = рк(п). (17)

Теорема 6.31. В предположении, что ао = 1, Ь<з = 0, существует набор таких Qi u bi е R, где 0 < i < к, что справедлив ряд соотношений вида pt(7t) = ai7t+bi.

Величины ai и bi вычисляются рекуррентно. Таким образом, уравнение (17) линейное; на основе его решения определяются вероятности p(x¡.) и p{x,-xt). Произведен анализ множества решений уравнения (17).

»—«>-('-«)• MSiílS!)-

Введенные матрицы и векторы являются стохастическими (вероятностными). Матрица W = Wk_i Wk-2 •.. Wj Wo также является стохастической.

Теорема 6.32. Матрично-векторное уравнение (18)

?ь =W7ib (18)

эквивалентно уравнению (17) с учетом введенных обозначений.

Из (18), в частности, следует, что ttq должен являться собственным вектором произведения матриц W, причем ему должно соответствовать собственное число А = 1, которому, в свою очередь, соответствует единственный стохастический вектор, исключая случай W = Е.

Теорема 6.33. Матрично-векторное уравнение (' 18j имеет либо одно, либо бесконечно много стохастических векторов-решений.

Следствие 6.1. Уравнение (17) имеет либо одно, либо бесконечно много решений 7Тб [0; 1].

Теорема 6.34. Матрично-векторное уравнение (18) имеет бесконечно много стохастических векторов-решений, а уравнение (17) — бесконечно много решений tí g [0; 1] тогда и только тогда, когда исходные условные вероятности в исходном БСД-цикле не принимают никакие другие значения, кроме 0 или 1, а число узлов с тензорами условных вероятностей, отвечающих условию p(xi|xj) = p(xi|xj) = 0, четно.

Замечание 6.1. На этапе перехода от набора условных вероятностей из исходного БСД-цикла к набору маргинальных вероятностей для соответствующего

ему цикла ФЗ АБС противоречие (несовместность) исходных данных не eti-явится. Процесс перехода завершится либо формированием набора маргинальных вероятностей, либо формированием непустого семейства таких наборов.

Предложено несколько методов преобразования ВСД-дикла в цикл смежности ФЗ. Ключевой метод состоит из двух основных фаз. На первой фазе распространяются сообщения, которые позволяют сформировать уравнение а^я + Ък — п. Следующий шаг — это анализ получившегося уравнения и поиск его решения, если оно единственное. Если такое решение найдено, то выполняется вторая фаза: в цикле от узла к узлу передаются и вычисляются маргинальные вероятности p(xi_ i ) и р(>ц_ i Xi ). Объем требующихся вычислений линеен по числу сообщений и по числу операций сложения, вычитания и умножения. Деление используется только один раз между первой и второй фазой.

В главе также рассматриваются особые случаи (БСД-цикл-петля, ВСД-цикл над двумя узлами), ВСД-цикл с многозначными элементами, обобщение цепного правила, лежащего в основе одного из определений байесовских сетей доверия, которое бы позволило сопоставить семейство распределений вероятностей байесовской сети доверия с направленным циклом. Это открывает возможность преобразования такой ВСД в алгебраическую байесовскую сеть, которая будет обладать той же же самой вероятностной семантикой. Приведены примеры непротиворечивых и противоречивых БСД-циклов. Наконец, в иллюстративных целях метод обработки направленного ВСД-цикла применен в решении задачи по оценке вероятности альтернатив при исходных данных, заданных в виде цикла стохастических предпочтений.

Глава 7 «Комплекс программ» содержит описание комплекса программ, автоматизирующего операции логико-вероятностного вывода в ABC и их ФЗ, реализованного с помощью среды разработки NetBeans за языке Java с использованием ряда java-технологий и внешних библиотек. Выбор языка, технологий и среды разработки был обусловлен их удобством, наличием в свободном доступе и особенностями представления и обработки данных, облегчающих, в свою очередь, представление и обработку объектов теории алгебраических байесовских сетей в компонентах комплекса.

В комплексе реализовано четыре основных блока функциональности.

Первый блок (AlgBN Modeler) обеспечивает представление алгебраических байесовских сетей и фрагментов знаний, а также альтернативных моделей фрагментов знаний в коде программ. Кроме того, он обеспечивает ряд операций по чтению-записи данных в соответствующие объекты, содержит ряд утилит, включая генераторы элементов матриц, использующихся в логико-вероятностном выводе, индексаторы конъюнктов, дизъюнктов и квантов, классы-коллекторы, позволяющие строить линейную комбинацию и линейную оболочку фрагментов знаний, классы, представляющие алфавиты, и др. Наконец, к этому блоку примыкают пакеты, отвечающие за представление вторичной структуры ABC в графическом пользовательском интерфейсе, и реляционная база данных, предназначенная для хранения алгебраических байесовских сетей, свидетельств, сессий, задающих конкретные операции логико-вероятностного вывода вместе с их объектами, и результатов выполнение этих операций, ассоциированных с указанными сессиями. Представление ABC и свидетельств в базе данных универсализовано для хранения различных их подвидов в одинаковых структурах.

Второй блок (AlgBN Inferrer) предназначен для выполнения синтеза согласованных оценок истинности в алгебраических байесовских сетях и их фрагментах, т.е. для проверки и поддержания непротиворечивости фрагмента знаний (в том числе фрагмента знаний с альтернативной структурой), локального априорного вывода, проверки и поддержания интернальной и глобальной степени непроти-

воречивости ABC. Второй блок оперирует объектами, построенными с помощью первого блока, и используется в апостериорном выводе.

Третий блок (AlgBN Propagator) реализует операции апостериорного вывода, а именно локальный апостериорный вывод с различным сочетанием видов априорных оценок и свидетельств, а также глобальный апостериорный вывод на основе распространения виртуальных свидетельств при поступлении стохастического свидетельства в ациклическую алгебраическую байесовскую сеть со скалярными оценками. Третий блок использует объекты и методы из в первых двух.

Четвертый блок (BBN Feedback Cycle OOJLib) позволяет преобразовать направленный БСД-цикл в набор оценок вероятностей атомов и конъюнкций пар атомов, расположенных в смежных узлах указанного цикла. Полученный набор оценок предназначен для формирования фрагмента знаний или цепи смежности фрагментов знаний, которые представляются и обрабатываются в программном коде с помощью функциональности, обеспеченной первыми тремя блоками.

Наконец, в главе приводятся примеры использования в программном коде объектов и методов из указанных блоков.

В заключении приводятся основные научные результаты диссертационного исследования, выносимые на защиту:

1) развита теория алгебраических байесовских сетей как логико-вероятностной графической модели баз фрагментов знаний с неопределенностью, позволяющая использовать указанные сети как средство представления и обработки таких знаний;

2) выведены матрично-векторные уравнения, устанавливающие связь между вероятностями элементов фрагмента знаний алгебраической байесовской сети и дискретной плотностью вероятности в соответствующем конечном вероятностном пространстве; разработан основанный ка указанных уравнениях метод проверки и поддержания непротиворечивости ФЗ ABC, а также метод априорного вывода в таком фрагменте знаний;

3) построена и проанализирована иерархия степеней непротиворечивости алгебраической байесовской сети (локальная, экстернальная, иктернальная, глобальная степени непротиворечивости), выявлена система связей между указанными степенями непротиворечивости, разработаны методы проверки и поддержания соответствия ABC требованиям интервальной и глобальной степеней непротиворечивости, оценена сложность алгоритмов, реализующих эти методы;

4) доказано, что непротиворечивость ФЗ и степень непротиворечивости ABC сохраняется относительно операций построения линейной комбинации и линейной оболочки; формально установлены существование и единственность минимального (по включению интервальных оценок вероятностей) результата операции «накрывающей непротиворечивости» в случае непротиворечивых исходных данных;

Б) разработаны метод локального апостериорного вывода для детерминированного свидетельства в случае скалярных оценок вероятности истинности и метод оценки чувствительности ненормированных результатов этого вида вывода к допустимой вариации оценок истинности на основе использования соответствующих матрично-векторных уравнений и неравенств; обобщен метод локального апостериорного вывода на случаи других сочетаний видов свидетельства и оценок; доказана непротиворечивость результатов локального апостериорного вывода в случае непротиворечивых исходных данных;

6) разработан основанный на использовании виртуальных свидетельств метод распространения влияния стохастического свидетельства, поступившего во фрагмент знаний ациклической алгебраической байесовской сети со скалярными оценками истинности, на другие фрагменты знаний; дана оценка сложности

алгоритмов, участвующих в реализации метода, и выявлена лежащая в основе указанного метода особенность вероятностной семантики ABC (справедливость гипотезы условной независимости); разработан метод преобразования ациклической байесовской сети доверия (со случайными бинарными элементами в узлах) в ациклическую байесовскую сеть с сохранением вероятностной семантики;

7) разработаны методы проверки и поддержания непротиворечивости фрагментов знаний с альтернативной структурой (ФЗ на основе идеала дизъюнктов, набора пропозиций-квантов, расширенный ФЗ);

8) разработан метод преобразования цикла фрагментов знаний ABC в цепь смежности фрагментов знаний и проверки непротиворечивости указанных объектов; оценена вычислительная сложность преобразования и проверки непротиворечивости для циклов с фрагментами знаний, пересекающимися только попарно; разработаны методы преобразования (с сохранением вероятностной семантики) направленного цикла байесовской сети доверия во фрагмент знаний ABC, в цикл смежности фрагментов знаний ABC и цепь смежности; разработан основывающийся на указанных преобразованиях метод проверки непротиворечивости направленного цикла байесовской сети доверия; построены контрпримеры, служащие доказательством того, что не существует ВСД-исчисления, которое бы позволило, с одной стороны, сохранить традиционную вероятностную семантику байесовской сети доверия, а с другой — допустить наличие направленного цикла в такой сети;

9) спроектирован и реализован с использованием среды NetBeans комплекс java-nporpaMM, поддерживающий представление алгебраических байесовских сетей и их фрагментов, а также выполнение описанных в диссертации операций логико-вероятностного вывода для проведения вычислительных экспериментов; кроме того, разработана структура реляционной базы данных, позволяющая хранить указанные объекты и результаты логико-вероятностного вывода; разработанная структура базы данных реализована в JavaDB.

Список литературы

1. Городецкий В. И. Алгебраические байесовские сети — новая парадигма экспертных систем // Юбилейный сборник трудов институтов Отделения информатики, вычислительной техники и автоматизации РАН. Т. 2. М.: РАН, 1993. С. 120-141.

2. Bool G. An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities. Cambridge: Macmillan / London: Walton & Maberly, 1854. (Reprinted in 1951, Dover Publications, New York.) 424 p.

3. Cowell R. G.{ Daund, A. Ph., Lauritzen $. L., Spiegelhalter D. J. Probabilistic Networks and Expert Systems. Berlin: Springer, 2003. 321 p.

4. Fagin R., Halpern J. Y.t Megiddo N. A Logic for Reasoning about Probabilities. Report RJ 6190 (60900) 4/12/88. pp. 1-41.

5. Fagin R., Halpern J. Y. Uncertainty, Belief, and Probability-2 // Proc. of the IEEE Symposium on Logic and Computer Science. 1991. Vol. 7. P. 160-173.

6. Halpern J. Y. Reasoning about uncertainty. Cambridge: The MIT Press, 2003. 483 p.

7. Jensen F. V. Bayesian Networks and Decision Graphs. NY.: Springer, 2001. 268 p.

8. Kindermann Я., Snell J. L. Markov Random Fields and Their Applications. Providence, RI: Amer. Math. Soc., 1980. 142 p.

9. Kyburg H. E.t Teng С. M. Uncertain inference. Cambridge: Cambridge University Press, 2001. 298 p.

10. Korb К. В., Nicholson A. E. Bayesian Artificial Intelligence. NY.: Chapman and Hall/CRC, 2004. 364 p.

11. Neapolitan R. B. Learning Bayesian Networks. Pearson Prentice Hall, 2003. 674 p.

12. Nilsson N. J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 47. Amsterdam: Elsevier Science Publishers B.V., 1986. P. 71-87.

13. Nilsson N. J. Probabilistic Logic Revisited 11 Artificial Intelligence. 1993. Vol. 59. Amsterdam: Elsevier Science Publishers B.V., 1993. P. 31-36.

14. Parsons S. Qualitative methods for reasoning under uncertainty. Cambridge, MS: The MIT Press, 2001. 506 p.

15. Perl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. NY etc.: Morgan Kaufmann Puhl., 1994. P. Б52.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Монографии, прошедшие научное рецензирование

16. Тулупъев А. Л. Алгебраические байесовские сети: теоретические основы и непротиворечивость. СПб.: СПИИРАН, 1995. 76 с.

17. Тулупъев А. Л. Алгебраические байесовские сети: логико-вероятностный подход к моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 282 с.

18. Тулупъев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.

19. Тулупъев А. Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петерб. ун-та, 2008. 140 с.

20. Тулупъев А. Л., Сироткин А. В., Николенко С. И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009. 400 с.

Статьи в изданиях, входивших на момент публикации в «Перечень ведущих рецензируемых научных журналов и изданий», рекомендованных ВАК

21. Городецкий В. И., Тулупъев А. Л. Формирование непротиворечивых баз знаний с неопределенностью // Известия РАН. Сер. Теория и системы управления. 1997. X« 5. С. 33-42.

22. Тулупъев А. Л. Генерация множества ограничений на распределение оценок вероятности над идеалом цепочек конъюнкций // Вестник молодых ученых. 2004. X« 4. Сер. Прикладная математика и механика. 2004. № 1. С. 35-43.

23. Тулупъев А. Л., Николенко С. Я., Сироткин А. В. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах //Известия высших учебных заведений; Приборостроение. 2006. № 7. С. 20—26.

24. Тулупъев А. Л., Николенко С. Я., Никитин Д. А., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: детерминированный вариант // Известия высших учебных заведений: Приборостроение. 2006. К' 11. С. 35-39.

25. Тулупъев А. Л., Николенко С. И., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: стохастический вариант // Известия высших учебных заведений: Приборостроение. 2006. № 11. С. 39-44.

26. Тулупъев А. Л., Сироткин А. В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. X« 10, т. 6. С, 85-87.

27. Тулупъев А. Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. № 3. С. 21-23.

28. Тулупъев А. Л. Алгебраические байесовские сети: система операций локального логико-вероятностного вывода // Информационно-измерительные и управляющие системы. 2009. K« 4. С. 41-44.

29. Тулупъев А. Л. Непротиворечивость оценок вероятностей в идеалах конъюнктов и дизъюнктов // Вестник СПбГУ. Сер. 10. 2009. Вып. 2. С. 121-131.

30. Тулупъев А. Л. Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. № 7. С. 3-7.

По теме диссертации с 1995 г. опубликованы в других изданиях 64 научные статьи и доклада, прошли государственную регистрацию во ВНТИЦ и одновременно — отраслевую регистрацию в ОФАП Госкоорцентра 6 программ для ЭВМ, еще 3 программы для ЭВМ прошли регистрацию в Роспатенте с получением Свидетельств об официальной регистрации программы, для ЭВМ. Копии регистрационных документов помещены в приложение к диссертации.

Подписано в печать 11.08.2009. Формат 60x84/16.

Бумага офсетная. Печать офсетная. ^ Объём 2,0 пен. л. Тираж 100 экз. Заказ №

Типография Издательства СПбГУ.

199061, С.-Петербург, Средний пр., 41.

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

Введение.

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

§1.1. Введение.

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

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

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

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

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

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

§ 1.8. Выводы по главе.

Глава 2. Байесовские сети доверия.

§2.1. Введение.

§ 2.2. Структура БСД и задача обработки свидетельств.

§ 2.3. Типы связей между узлами сети и d-разделимость.

§ 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. Свойства непротиворечивых ABC.

§ 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. Выводы по главе.

Актуальность темы. Подводя итоги одного из этапов многолетнего изучения моделей знаний с неопределенностью, В.И. Городецкий в 1993 году ввел алгебраические байесовские сети (АБС) в область исследований искусственного интеллекта (ИИ) как новую парадигму экспертных систем [40].

Источником особого научного интереса к указанным моделям послужил анализ проблем, существенно замедляющих прогресс в области масштабных промышленных внедрений экспертных систем. Были выявлены, в частности, два вида дефицита: дефицит математических моделей для представления знаний с неопределенностью (uncertain knowledge representation bottleneck) и просто дефицит знаний (knowledge bottleneck) [159,162,165,187,332]. Интенсивно развивающиеся в рамках ИИ теории вероятностных графических моделей1 (ВГМ) вносят существенный вклад в поиск и разработку путей преодоления дефицита двух указанных видов, а также ряда смежных проблем.

Теории ВГМ [40,250,308,320,329,332,343,365,381,390] предлагают как новые модели для представления систем знаний с неопределенностью, т.е. позволяют смягчить влияние дефицита первого вида, так и новые подходы к алгоритмизации машинного обучения (machine learning, синоним — автоматическое обучение) таких моделей на основе накопления и обработки разнородных исходных данных, сведений или знаний с неопределенностью (в частности, отличающихся неполнотой, неточностью и имеющих нечисловой характер). Машинное обучение позволяет обойти ряд препятствий, создаваемых дефицитом второго вида. Помимо этого, в теориях ВГМ с помощью методов математики и информатики исследуются предложенные модели данных и знаний с неопределенностью, принципы создания и

1 Термин вероятностные графические модели является переводом англоязычного probabilistic graphical models. Нельзя не признать, что в русскоы языке термин графическая модель воспринимается, скорее, как визуальная модель, например как чертеж, схема или эскиз. В силу этого подчеркнем, что в настоящем диссертационном исследовании термин графические людели обозначает математические модели, основу которых составляют графы. функционирования программных средств, позволяющих представить эти модели в памяти компьютера, а также автоматизировать процессы их формирования, хранения, обработки и обучения.

К ВГМ, нацеленным в первую очередь на решение очерченных и ряда смежных проблем, в рамках искусственного интеллекта можно причислить байесовские сети доверия (введены J. РеагГом) [156,178,187,250,320,332,365,390], в некоторой степени — марковские сети (были «импортированы» из статистической физики, где классическим примером их применения является модель Изинга в изучении магнетизма) [156,329], а также алгебраические байесовские сети (введены В. И. Городецким) [40]). Следует отметить, что в теории байесовских сетей доверия (БСД) остаются открытыми вопросы, связанные с обработкой направленных циклов и интервальных оценок вероятностей; кроме того, вероятностный вывод не может осуществляться непосредственно в БСД с многосвязной структурой — такую сеть требуется предварительно преобразовать в дерево сочленений.

Теория алгебраических байесовских сетей занимает свое место среди теорий ВГМ и решает общие с ними задачи, а сами алгебраические байесовские сети имеют ряд отличительных особенностей и в первую очередь могут быть охарактеризованы как логико-вероятностные графические модели (ЛВГМ) баз фрагментов знаний (БФЗ) с неопределенностью [141-143,148-150,162,178,182,184,187].

Основной принцип, лежащий в основе ВГМ, хорошо известен — это принцип декомпозиции. Он применяется к совокупности знаний о предметной области. Считается, что эксперт может достаточно детально охарактеризовать связи между двумя-тремя-четырьмя утверждениями о предметной области [390] — в каком-то смысле получается «фрагмент знаний» (ФЗ). Таких фрагментов знаний много, они образуют БФЗ. Однако фрагменты знаний и их базы нельзя напрямую заложить в интеллектуальную информационную систему или комплекс программ. Сначала требуется рассмотреть математические модели ФЗ и БФЗ, разработать соответствующие структуры данных и снабдить их алгоритмами обработки. Получающиеся модели должны обладать некоторой «регулярностью» структуры, общностью принципов построения своих элементов, чтобы можно было использовать одни и те же алгоритмы вывода как на локальном уровне (т.е. на уровне фрагментов знаний), так и на глобальном (т.е. на уровне всей базы).

С математической точки зрения возникающие объекты могут быть рассмотрены как система случайных элементов, которая, как правило, организована в виде графа со специфическими свойствами или решетки (отсюда — графическая модель). Случайные элементы в системе могут быть связаны друг с другом, оказывать влияние на означивания других случайных элементов; однако связи между ее компонентами предполагаются достаточно редкими, немногочисленными, разреженными (sparse) [250,320,390].

Декомпозиция системы знаний дает преимущества и на психологическом (экспертном или пользовательском) уровне, поскольку получающаяся математическая модель структурирована и обозрима, и на технологическом, поскольку уменьшаются необходимые для хранения модели объемы памяти и вычислительная сложность алгоритмов ее обработки как на локальном, так и на глобальном уровне. Структурированность и обозримость ВГМ также видятся ее преимуществом при представлении сложных связей, выявленных классическим статистическим анализом или интеллектуальным анализом данных (data mining) [58,171,187,332,365].

Особый интерес с точки зрения моделирования процесса размышлений (reasoning) [308,343,381] специалиста-эксперта представляет логико-вероятностный подход, в котором моделью утверждения являются пропозициональные формулы (заданные над определенным алфавитом), что традиционно для формальной логики, а степень уверенности в истинности (или стохастическая неопределенность истинности) этих пропозициональных формул и сила связей между ними характеризуется с помощью оценок вероятностей: как скалярных (точечных), так и интервальных.

В своем современном виде логико-вероятностный подход был достаточно последовательным образом внесен в область исследований искусственного интеллекта Н. Нильссоном [371] и развит Фейгиным, Хальперном и Меггидо [274,276]. Приоритет Н. Нильссона, как он сам отмечает [373], был неоднократно оспорен. Анализируя позиции сторон спора о приоритетах, нельзя упускать из виду того, что еще в 1854 г. Дж. Буль [231] пытался применить вероятность как меру истинности (или как степень доверия к истинности) пропозициональных формул. Он сформулировал ряд проблем, которыми занимаются исследователи в области вероятностной логики и неопределенности в искусственном интеллекте по сей день.

Хотя логико-вероятностный подход имеет длительную историю, остается актуальным решение комплекса проблем, наделенных на его применение в интеллектуальных информационных системах: сначала требуется разработать в рамках указанного подхода математические модели (допускающие интервальные оценки вероятности истинности) БФЗ с неопределенностью с тем, чтобы по ним в свою очередь можно было бы построить структуры данных для представления накопленных знаний; затем автоматизировать ряд операций логико-вероятностного вывода: проверка и поддержание непротиворечивости ФЗ и БФЗ, априорный вывод во фрагменте знаний, апостериорный вывод (распространение влияние свидетельства) в ФЗ и БФЗ; наконец, исследовать сформированные модели и структуры данных, а также обосновать корректность и изучить некоторые свойства как разработанных методов формирования непротиворечивых ФЗ и БФЗ, вывода априорных и апостериорных оценок в них, так и получаемых с помощью указанных методов результатов.

Объект исследования — алгебраические байесовские сети, представляющие собой, с одной стороны, набор идеалов конъюнктов со скалярными или интервальными оценками вероятности истинности, причем указанный набор идеалов структурирован как граф смежности, а с другой стороны, логико-вероятностную графическую модель баз фрагментов знаний со стохастической (вероятностной) неопределенностью.

Цель исследования — на основе логико-вероятностного подхода к представлению неопределенности в интеллектуальных системах, предложенного Н. Нильс-соном, развить теорию алгебраических байесовских сетей как математических моделей знаний с вероятностной неопределенностью, допускающих декомпозицию на фрагменты ограниченного размера, для формирования научных основ современных информационных технологий, позволяющих решить проблему автоматизации логико-вероятностного вывода в указанных сетях. Для достижения указанной цели необходимо решить следующие основные задачи:

1) формализовать с использованием логико-вероятностного подхода в рамках теории АБС математические модели фрагмента знаний, базы фрагментов знаний и свидетельства, а также выявить вероятностную семантику этих объектов посредством анализа взаимосвязи входящих в них оценок вероятностей конъюнктов и дискретной плотности вероятности на соответствующем конечном вероятностном пространстве;

2) сформировать систему понятий, характеризующих состояние непротиворечивости фрагмента знаний и АБС; раскрыть отношения этих состояний; разработать методы их проверки и поддержания как в локальном, так и в глобальном случае (для интернальной и глобальной степеней непротиворечивости АБС), а также проанализировать влияние операций построения линейной комбинации и линейной оболочки на указанные состояния непротиворечивости;

3) формализовать локальный априорный вывод, проанализировать его взаимосвязь с поддержанием непротиворечивости, разработать метод локального априорного вывода в случае формулы, представленной в виде совершенной дизъюнктивной нормальной формы (СДНФ), и метод анализа чувствительности его результата к допустимым вариациям исходных данных в случае скалярных оценок;

4) формализовать апостериорный вывод; разработать метод реализации его локального варианта в случае детерминированного свидетельства и обобщить полученный результат для двух: других видов свидетельств; исследовать чувствительность ненормированного результата локального апостериорного вывода по детерминированному свидетельству в случае скалярных оценок; исследовать результаты локального апостериорного вывода с точки зрения их непротиворечивости при непротиворечивых исходных объектах; разработать метод распространения влияния стохастического свидетельства в ациклической АБС со скалярными оценками на основе «передачи» виртуальных свидетельств; выявить предположения о вероятностной семантике такой АБС, на которые опирается указанный метод, оценить сложность алгоритмов, его реализующих;

5) разработать метод преобразования ациклической байесовской сети доверия со случайными бинарными элементами в узлах в ациклическую алгебраическую байесовскую сеть; выявить отношение их вероятностных семантик;

6) проанализировать вероятностную семантику цикла смежности фрагментов знаний в АБС, разработать методы его преобразования в цепь смежности и проверки его непротиворечивости; с помощью полученных результатов выявить вероятностную семантику направленного цикла в теории БСД (БСД-цикла) и разработать для такого цикла метод проверки его непротиворечивости;

7) формализовать две альтернативные математические модели фрагментов знаний (на основе идеала дизъюнктов и набора квантов), разработать метод проверки и поддержания их непротиворечивости;

8) спроектировать и реализовать комплекс программ для проведения вычислительных экспериментов с исследованными в диссертации операциями логико-вероятностного вывода в АБС и их фрагментах, а также разработать структуру реляционной базы данных, ориентированную на хранение АБС, фрагментов знаний, свидетельств и результатов логико-вероятностного вывода.

Выбор вероятностной семантики исследуемых в диссертационной работе объектов теории АБС, определений и методов выполнения операций логико-вероятностного вывода, получения оценок чувствительности ограничивается дополнительным 1 требованием, выражающемся в том, чтобы все возникающие в процессе логико-вероятностного вывода экстремальные задачи допускали сведение к решению задачи (или серии задач) линейного программирования.

Методы исследования. В обзорно-аналитической и теоретической части исследования используются объекты и методы алгебры (линейной алгебры, теории частично упорядоченных множеств, булевой алгебры), теории вероятностей и вероятностной логики, теории графов, экстремальных задач (задачи линейного и гиперболического программирования), комбинаторики, мягких вычислений (преимущественно различные «меры» истинности), а также элементы теории потенциалов, теории марковских цепей, метода Монте-Карло. В программно-технологической части исследования используются теория реляционных баз данных, принципы структурного и объектно-ориентированного программирования (как в разработке структур данных, так и в реализации кода), а также ряд технологий, связанных с языком реализации (Java), средой разработки (NetBeans), СУБД (JavaDB). Само диссертационное исследование по своему объекту и методам, использованным для решения ряда задач по построению моделей и обработке знаний с вероятностной неопределенностью, относится к разделу искусственного интеллекта, изучающему и развивающему средства представления знаний.

Научная новизна. В диссертации формализована и исследована новая логико-вероятностная графическая модель баз фрагментов знаний с неопределенностью — алгебраические байесовские сети, чья глобальная структура задается в виде графа смежности (или его подвидов: дерева смежности, цепи смежности, цикла смежности), в узлах которого расположены идеалы конъюнктов со скалярными или интервальными оценками вероятности истинности, что отличает указанную модель от других вероятностных графических моделей (в частности, от байесовских сетей доверия и марковских сетей) и позволяет с ее помощью представлять, агрегировать и обрабатывать знания с неопределенностью посредством ряда операций логико-вероятностного вывода: поддержания и проверки непротиворечивости, априорного вывода, апостериорного вывода, причем в последнем допускается использование как детерминированных свидетельств, так и стохастических и неточных свидетельств, компоненты которых могут быть зависимыми.

Осуществлен вывод матрично-векторных уравнений, связывающих оценки вероятностей элементов идеала конъюнктов с дискретной плотностью вероятности соответствующего конечного вероятностного пространства, что позволило в свою очередь разработать и описать на матрично-векторном языке методы проверки и поддержания непротиворечивости фрагмента знаний АБС, априорного и апостериорного вывода в нем и исследовать чувствительность результатов двух последних, а также обобщить указанный метод проверки и поддержания непротиворечивости на фрагменты знаний с альтернативной структурой.

Разработаны методы глобального логико-вероятностного вывода в АБС, позволяющие проверять и поддерживать интернальную и глобальную степени непротиворечивости АБС (причем указаны условия, при которых интернальная степень непротиворечивости обеспечивает глобальную степень непротиворечивости), а также позволяющие распространить влияние стохастического свидетельства, поступившего во фрагмент знаний ациклической алгебраической байесовской сети со скалярными оценками, на другие входящие в нее ФЗ; получены оценки вычислительной сложности соответствующих алгоритмов.

Обнаружено и формально обосновано свойство сохранения состояния непротиворечивости фрагментов знаний и степеней непротиворечивости алгебраических байесовских сетей по отношению к операциям линейной комбинации и линейной оболочки. Кроме того, доказано, что линейная оболочка будет единственным минимальным (по вхождению оценок-интервалов) результатом операции «накрывающей» непротиворечивости, примененной к совокупности непротиворечивых фрагментов знаний (или отвечающих требованиям заданной степени непротиворечивости алгебраических байесовских сетей) одинаковой структуры.

Выявлена вероятностная семантика и предложен метод преобразования направленного цикла байесовской сети доверия в цикл смежности и цепь смежности фрагI ментов знаний АБС, что в свою очередь позволило разработать метод проверки непротиворечивости исходного цикла; получены оценки вычислительной сложности соответствующих алгоритмов. Разработан метод преобразования ациклической байесовской сети доверия с бинарными случайными элементами в узлах в ациклическую алгебраическую байесовскую сеть.

На языке Java и с использованием java-технологий спроектирован и реализован комплекс программ, позволяющий выполнять исследованные в диссертации операции логико-вероятностного вывода с АБС, их фрагментами и свидетельствами с целью проведения вычислительных экспериментов; кроме того, на основе реляционной СУБД JavaDB реализована база данных, ориентированная на хранение указанных объектов и результатов логико-вероятностного вывода.

Все основные научные результаты, полученные в процессе диссертационного исследования и выносимые на защиту, являются новыми.

Диссертационное исследование выполнялось согласно плешам СПИИРАН по научному направлению «Теоретические основы построения информационных технологий для интеллектуальных систем автоматизации научных исследований, управления, производства и других сфер деятельности».

Апробация.Результаты диссертационного исследования докладывались и обсуждались на следующих научных мероприятиях: 1) Международная конференция «Знания-Диалог-Решение-95», Ялта, 1995; 2) IV Санкт-Петербургская международная конференция «Региональная информатика-95», Санкт-Петербург, 1995; 3) Всероссийская научно-техническая конференция «Электроника и информатика», Москва, 1995;. 4) Международная конференция «Эволюция инфосферы-95», Москва, 1995; 5) Шестая национальная конференция по искусственному интеллекту с международным участием КИИ'98, Пущино, 1998; 6) VII Санкт-Петербургская международная конференция «Региональная информатика-2000 (РИ-2000)», Санкт-Петербург, 2000; 7) Международный научно-практический семинар «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна,

2001; 8) Всероссийская научно-практическая конференция «Информатика и информационные технологии в образовании», Санкт-Петербург, 2001; 9) XI Межгосударственная школа-семинар «Синтез и сложность управляющих систем», Москва, 2001; 10) Международный банковский конгресс и Международная научно-практическая конференция, Санкт-Петербург, 2001; 11) Международная научная школа «Моделирование и анализ безопасности и риска в сложных системах», Санкт-Петербург, 2002. 12) Всероссийская научно-практическая конференция «Информатика и информационные технологии в образовании», Санкт-Петербург, 2002; 13) Научная сессия МИФИ-2002, Москва, 2002; 14) VIII Санкт-Петербургская международная конференция «Региональная информатика-2002», Санкт-Петербург, 2002; 15) IX Санкт-Петербургская международная конференция «Региональная информатика-2004», Санкт-Петербург, 2004; 16) Научная сессия МИФИ-2005, Москва, 2005; 17) III международный научно-практический семинар «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Пущино, 2005 18) Mexican International Conference on Artificial Intelligence, Mexico, 2005; 19) Конференция «Мягкие вычисления и измерения», Санкт-Петербург, 2005; 20) Всероссийская научная конференция по нечетким системам и мягким вычислениям, Тверь, 2006; 21) Научная сессия МИФИ-2006, Москва, 2006; 22) X Санкт-Петербургская международная конференция «Региональная информатика - 2006», Санкт-Петербург, 2006; 23) Научная конференция МИФИ-2007, Москва, 2007; 24) Международная конференция по мягким вычислениям и измерениям - 2007; Санкт-Петербург, 2007; 25) IV международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 2007; 26) V Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России», Санкт-Петербург, 2007; 27) Научная сессия МИФИ-2008, Москва, 2008; 28) Научная конференция «Информационные технологии и системы-2008», Геленджик, 29 сентября - 03 октября, 2008 г.; 29) Вторая Всероссийская научная конференция с международным участием «Нечеткие системы и мягкие вычисления» (НСМВ-2008), г. Ульяновск, 27-29 октября 2008 г.; 30) XI Санкт-Петербургская международная конференция «Региональная информатика - 2008», Санкт-Петербург, 2008; 31) Научная сессия МИФИ-2009, Москва, 2009; 32) Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009), Коломна, 26-27 мая 2009 г.; 33) V-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 28-30 мая 2009 г.; 34) Международная конференция по мягким вычислениям и измерениям SCM-2009, Санкт-Петербург, 25-27 июня 2009 г.; 35) Санкт-Петербургский городской научный семинар «Информатика и компьютерные технологии» (многократно в 1996-2001 и 2004-2009 гг.).

Достоверность полученных в диссертационном исследовании результатов обоснована корректностью применения методов соответствующих математических дисциплин. Дополнительным аргументом в пользу достоверности результатов диссертационного исследования является работоспособность комплекса программ, реализующего операции логико-вероятностного вывода в алгебраических байесовских сетях и их фрагментах.

Теоретическая и практическая значимость исследования. Реализация результатов работы. Диссертация носит преимущественно теоретический характер. Модели и методы, разработанные в ней, позволят спроектировать и реализовать средства представления знаний со стохастической (вероятностной) неопределенностью в интеллектуальных системах и комплексах программ. При этом реализация таких комплексов облегчается тем, что они могут использовать уже существующие программные технологии и библиотеки программ (в частности, библиотеки для решения задач линейного программирования). В процессе исследования для проведения численных экспериментов был разработан комплекс программ, позволяющий представить и обработать объекты, а также выполнить операции логико-вероятностного вывода, описанные в диссертации. (Компоненты комплекса зарегистрированы [125-131,169,172]; копии регистрационных документов помещены в приложение к диссертации.)

Второй составляющей теоретической и практической значимости является возможность исследовать на непротиворечивость и обработать структуры, недопустимые в рамках теории байесовских сетей доверия, но возникающие на практике (направленные циклы). С теоретической точки зрения важен результат о невозможности построения исчисления байесовских сетей доверия, одновременно допускающего обработку направленных циклов и сохраняющего традиционную вероятностную семантику байесовских сетей доверия (единственность глобального распределения и согласованность с ним тензоров условных вероятностей в узлах сети).

Третьей составляющей практической значимости полученных теоретических результатов является возможность их применения в альтернативном способе расчетов надежности фрагментов структурно-сложных систем или для оценки надежности таких фрагментов в случае интервальных исходных данных и в случае недоопре-деленных, но реально существующих или потенциально возможных зависимостей между выходами из строя элементов, ранее полагавшихся независимыми. (Имеется акт о внедрении от ОАО СПИК СЗМА; копия гнета помещена в приложение к диссертации.)

Четвертой составляющей практической значимости является возможность применения теории алгебраических байесовских сетей и разработанного комплекса программ в решении задач поддержки принятия решений, в частности для представления и обработки неточной, неполной, нечисловой информации о соотношении вероятностей истинности утверждений, на основе которых принимаются решения, и для комбинирования или агрегирования такой информации из источников, степени доверия к которым могут различаться или быть неизвестными.

Наконец, важной составляющей практической значимости является использование теории алгебраических байесовских сетей в преподавании дисциплин, посвященных научным основам современных информационных технологий и подходам к разработке интеллектуальных систем, в вузах, где осуществляется подготовка студентов и аспирантов соответствующих специальностей. (Имеются акты об использовании в учебном процессе от СПбГУ и от СПбГУ ИТМО; копии актов помещены в приложение к диссертации.)

Дополнительным свидетельством реализации результатов диссертационного исследования, а также аргументом в пользу его научной значимости и актуальности служит поддержка, полученная соискателем в форме стипендий и грантов. Исследования по теме диссертации были дважды поддержаны Государственной стипендией для талантливых молодых ученых (1998-2000, 2000-2002), четырежды — грантом Фонда содействия отечественной науке по программе «Молодые кандидаты и доктора наук. Выдающиеся учёные РАН» (2004, 2005, 2006, 2007), грантом РФФИ (09-01-00861-а — «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью»), и, наконец, госконтрактом 02.442.11.7289 от 28.02.2006 на выполнение НИР «Направленные циклы в байесовских сетях доверия: вероятностная семантика и алгоритмы логико-вероятностного вывода для программных комплексов с байесовской интеллектуальной компонентой» в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы».

Издание монографии [178] соискателя «Байесовские сети: логико-вероятностный подход», СПб.: Наука, 2006, (в соавторстве, с С. И. Николенко и А. В. Сироткиным) было поддержано грантом РФФИ № 06-01-14108-д, а в 2007 г. ее авторский коллектив стал лауреатом конкурса на лучшую научную книгу 2006 года (Фонд развития отечественного образования, г. Сочи).

Публикации. По теме диссертации опубликовано 87 научных работ, из них 5 монографий (3 единоличные и 2 в соавторстве), прошедших научное рецензирование, 9 статей в изданиях из «Перечня ведущих рецензируемых научных журналов и изданий», 64 научные статьи и доклада на конференциях, 9 зарегистрированных программ для ЭВМ. Сверх указанного по теме диссертации было опубликовано 2 учебных пособия, также прошедших научное рецензирование, и ряд тезисов научных докладов.

Личный вклад А.Л. Тулупьева в публикациях с соавторами характеризуется следующим образом. В монографиях [178,187] А.Л. Тулупьеву принадлежат все результаты, характеризующие вероятностную семантику алгебраических байесовских сетей и их фрагментов, уравнения и методы локального и глобального логико-вероятностного вывода в алгебраических байесовских сетях, результаты о линейной комбинации и линейной оболочке алгебраических байесовских сетей и их фрагментов знаний, формализация операции «накрывающей» непротиворечивости, результаты о «накрывающей» непротиворечивости в части, относящейся к совокупности непротиворечивых объектов, анализ вероятностной семантики циклов в алгебраических байесовских сетях и байесовских сетях доверия, методы преобразований и обработки этих циклов, определения и анализ свойств степеней непротиворечивости АБС, алгоритмы проверки и поддержания интернальной и глобальной степени непротиворечивости этих сетей, результат о невозможности обработать направленный цикл в байесовской сети с «традиционной» вероятностной семантикой, обобщения алгебраических байесовских сетей на другие формализмы, позволяющие приписывать пропозициональным формулам оценки истинности, подход к анализу чувствительности локальных априорного и апостериорного вывода (в том числе посредством исследования соответствующих матрично-векторных уравнений), формализация задач, проектирование программ и реализация структур данных в них, определение различных видов свидетельств, анализ их вероятностной семантики, алгоритмы их обработки и распространения в АБС, анализ и алгоритм преобразования ациклической байесовской сети доверия в алгебраическую байесовскую сеть, исследование взаимосвязи априорного вывода и поддержания непротиворечивости, определение, анализ вероятностной семантики расширенного фрагмента знаний и фрагментов знаний с альтернативной структурой, матрично-векторные уравнения и алгоритмы проверки и поддержания их непротиворечивости и априорного вывода в таких фрагментах знаний, а также диссертантом предложены уравнения и алгоритмы для локального машинного обучения алгебраических байесовских сетей, алгоритм восстановления вторичной структуры алгебраической байесовской сети по ее первичной структуре. На основе полученных А.Л. Тулупьевым результатов А.В. Сироткин выявил структуру матрицы, участвующей в матрично-векторном уравнении локального апостериорного вывода, привел теоретические оценки устойчивости поддержания непротиворечивости, реализовал часть программного кода, привел дискриминант-пример, разделяющий интернальную и экстернальную степень непротиворечивости алгебраических байесовских сетей, разработал алгоритм построения алгебраической байесовской сети, являющейся семантически эквивалентным образом байесовской сети доверия с допустимыми (ненаправленными) циклами, разработал алгоритм поддержания экстернальной непротиворечивости ациклической алгебраической байесовской сети, уточнил формализацию объемлющей непротиворечивости и исследовал ее в случае противоречивых исходных данных. С.И. Николенко сосредоточился на работе с байесовскими сетями доверия в аспектах, не входящих в объект диссертационных исследований А.Л. Тулупьева и А.В. Сироткина. Такое же соотношение тематики результатов и вкладов (в их релевантной каждой конкретной работе части) сохранялось во всех совместных публикациях с А.В. Сироткиным и С.И. Николенко, в частности, в [177,179,180,182].

В совместных публикациях с В.И. Городецким, в том числе, в [46], Тулупье-ву А.Л. принадлежит анализ свойств обсуждаемых в статьях объектов (преимущественно алгебраических байесовских сетей, их фрагментов, а также непротиворечивости этих объектов), а В.И. Городецкому — содержательная формальная постановка задач и указание возможных приложений обсуждаемых формализмов и объектов для решения задач искусственного интеллекта в области инженерии знаний.

В работах, совместных с Д.А. Никитиным, Тулупьеву А.Л. принадлежат результаты, относящиеся к алгебраическим байесовским сетям, а Д.А. Никитину — классификация и результаты исследования возникающих в процессе логико-вероятностного вывода экстремальных задач. В работах, совместных с М.Н. Ромашовой Тулупьеву А.Л. принадлежат результаты, относящиеся к алгебраическим байесовским сетям и их компаративному анализу с сетями, где в качестве меры истинности использовались нечеткие меры; М.Н. Ромашова сосредоточилась на исследовании устойчивости нечеткого вывода в соответствующих сетях фрагментов нечетких знаний. В работах, совместных с А.В. Тишковым, Д.П. Лакомовым, Тулупьеву А.Л. принадлежат результаты, относящиеся к алгебраическим байесовским сетям, а соавторам — обобщение АБС на случай дискретных оценок истинности и анализ геометрических особенностей множества допустимых планов, задаваемых ограничениями в ФЗ и в АБС. В работах с А.К. Абрамян Тулупьеву А.Л. принадлежат теоретические результаты, относящиеся к АБС и направленным циклам в байесовских сетях доверия, формализация задач для разработки программ, а А.К. Абрамян — реализация разработанных А.Л. Тулупьевым алгоритмов и подбор иллюстративных примеров. Работа [124] выполнена А.Л. Тулупьевым, соавторам принадлежат результаты тестирования и реинжиниринга программного обеспечения, разработка диаграмм и схем по готовому коду и спецификациям, формирование иллюстративных примеров.

В статье [68] Тулупьеву А.Л. принадлежит характеристика АБС как моделей знаний с неопределенностью, допускающих систематическую обработку интервальных оценок истинности; остальные результаты принадлежат соавторам. В статьях [58,171] Тулупьеву А.А. принадлежит формализация отношений в системе «Личность-Деятельность-Эффективность» с помощью алгебраических байесовских сетей и байесовских сетей доверия, а остальные результаты принадлежат соавторам.

В статье [188] Тулупьеву А.Л. принадлежат теоретические результаты, формализация построения вторичной структуры АБС, проект комплекса программ, позволяющих представить фрагменты знаний алгебраических байесовских сетей в программном коде, остальные результаты принадлежат соавторам. В работе [73] Тулу-пьев А.Л. предложил алгоритм формирования оценок вероятностей в алгебраической байесовской сети на основе статистических данных, поступающих при анализе текстов; А.В. Лобацевичу принадлежат остальные результаты.

В совместных программных разработках [169,172] А.Л. Тулупьеву принадлежит формализация задач, проект программной системы, реализация структур данных в виде объектов, спецификация методов. Реализация кода большей части методов принадлежит соавторам А.Л. Тулупьева.

Структура и объем работы. Диссертация состоит из введения, 7 глав, заключения, перечня сокращений, библиографии, списка таблиц, иллюстраций и примеров, а также предметного указателя и приложений. Общий объем работы составляет 670 страниц. Библиография содержит более 450 наименований. В приложения вынесены часть примеров, копии регистрационных документов и актов о внедрении (использовании), а также иной материал, являющийся справочным, иллюстративным или дополняющим основной.

Заключение

Приведем основные научные результаты диссертационного исследования, выносимые на защиту:

1) развита теория алгебраических байесовских сетей как логико-вероятностной графической модели баз фрагментов знаний с неопределенностью, позволяющая использовать указанные сети как средство представления и обработки таких знаний;

2) выведены матрично-векторные уравнения, устанавливающие связь между вероятностями элементов фрагмента знаний алгебраической байесовской сети и дискретной плотностью вероятности в соответствующем конечном вероятностном пространстве; разработан основанный на указанных уравнениях метод проверки и поддержания непротиворечивости ФЗ АБС, а также метод априорного вывода в таком фрагменте знаний;

3) построена и проанализирована иерархия степеней непротиворечивости алгебраической байесовской сети (локальная, экстернальная, интернальная, глобальная степени непротиворечивости), выявлена система связей между указанными степенями непротиворечивости, разработаны методы проверки и поддержания соответствия АБС требованиям интернальной и глобальной степеней непротиворечивости, оценена сложность алгоритмов, реализующих эти методы;

4) доказано, что непротиворечивость ФЗ и степень непротиворечивости АБС сохраняется относительно операций построения линейной комбинации и линейной оболочки; формально установлены существование и единственность минимального (по включению интервальных оценок вероятностей) результата операции «накрывающей» непротиворечивости в случае непротиворечивых исходных данных;

5) разработаны метод локального апостериорного вывода для детерминированного свидетельства в случае скалярных оценок вероятности истинности и метод оценки; чувствительности ненормированных результатов этого вида вывода к допустимой вариации оценок истинности на основе использования соответствующих матрично-векторных уравнений и неравенств; обобщен метод локального апостериорного вывода на случаи других сочетаний видов свидетельства и оценок; доказана непротиворечивость результатов локального апостериорного вывода в случае непротиворечивых исходных данных;

6) разработан основанный на использовании виртуальных свидетельств метод распространения влияния стохастического свидетельства, поступившего во фрагмент знаний ациклической алгебраической байесовской сети со скалярными оценками истинности, на другие фрагменты знаний; дана оценка сложности алгоритмов, участвующих в реализации метода, и выявлена лежащая в основе указанного метода особенность вероятностной семантики АБС (справедливость гипотезы условной независимости); разработан метод преобразования ациклической байесовской сети доверия (со случайными бинарными элементами в узлах) в ациклическую байесовскую сеть с сохранением вероятностной семантики;

7) разработаны методы проверки и поддержания непротиворечивости фрагментов знаний с альтернативной структурой (ФЗ на основе идеала дизъюнктов, набора пропозиций-квантов, расширенный ФЗ);

8) разработан метод преобразования цикла фрагментов знаний АБС в цепь смежности фрагментов знаний и проверки непротиворечивости указанных объектов; оценена вычислительная сложность преобразования и проверки непротиворечивости для циклов с фрагментами знаний, пересекающимися только попарно; разработаны методы преобразования (с сохранением вероятностной семантики) направленного цикла байесовской сети доверия во фрагмент знаний АБС, в цикл смежности фрагментов знаний АБС и цепь смежности; разработан основывающийся на указанных преобразованиях метод проверки непротиворечивости направленного цикла байесовской сети доверия; построены контр-примеры, служащие доказательством того, что не существует БСД-исчисления, которое бы позволило, с одной стороны, сохранить традиционную вероятностную семантику байесовской сети доверия, а с другой, допустить наличие направленного цикла в такой сети;

9) спроектирован и реализован с использованием среды NetBeans комплекс java-программ, поддерживающий представление алгебраических байесовских сетей и их фрагментов, а также выполнение описанных в диссертации операций логико-вероятностного вывода для проведения вычислительных экспериментов; кроме того, разработана структура реляционной базы данных, позволяющая хранить указанные объекты и результаты логико-вероятностного вывода; разработанная структура базы данных реализована в JavaDB.

1. Абакаров А. Ш., Сушков Ю. А. Принятие решений. Метод анализа иерархий. М.: Радио и связь, 1993. 316 с.

2. Абрамян А. К., Тулупъев А. Л. Логико-вероятностный вывод в идеалах конъюнктов: Java- и ILOG-технологии // Научная конференция МИФИ. 2007. Материалы. Т. 3. М.: МИФИ, 2007. С. 104-105.

3. Аверкин А. Н. Модели приближенных рассуждений: обзор зарубежных исследований // Новости искусственного интеллекта. 1991. Т. 3. С. 85-92.

4. Аверкин А. Н. Экспертные системы, использующие нечеткие и неопределенные знания // Нетрадиционные модели и системы с нечеткими знаниями / Под ред. А. Ф. Блишуна. М.: Энергоатомиздат, 1991. С. 12-20.

5. Аверкин А. Н. Извлечение нечетких логик в нечетких экспертных системах // Искусственный интеллект-94. Сборник научных трудов. Рыбинск, 1994. С. 207-211.

6. Аверкин А. Н., Костерев В. В. Триангулярные нормы в системах искусственного интеллекта // Изв. РАН. Сер. Теория и системы управления. 2000. № 5. С. 107-119.

7. Аверкин А. Н., Нгуен М. X. Использование нечетких отношений в моделях представления знаний Ц Изв. АН СССР. Сер. Техническая кибернетика. 1990. Т. 5. С. 20-33.

8. Аверкин А. Н. и др. Нечеткие множества в моделях управления и искусственном интеллекте. М.: Наука, 1986. 312 с.

9. Алёшина Н. А. О некоторых системах вероятностной логики // Искусственный интеллект и проблемы организации знаний. 1991. Т. 8. С. 78-85.

10. Алиев Р. А. Интеллектуальные роботы с нечеткими базами знаний. М.: Радио и связь, 1995. 178 с.

11. Антонюк Б. Д. Разработка экспертных систем искусственного интеллекта в США. М., 1985. 78 с.

12. Батыршин И. 3. О некоторых свойствах мер невероятностной энтропии размытых множеств // Прикладной многомерный статистический анализ. М.:Наука, 1978. С. 345348.

13. Батыршин И. 3. О транзитивности размытых упорядочений // Исследование опер-ций и аналитическое проектирование в технике. Казань, 1979. С. 67-73.

14. Батыршин И. 3. Нечеткие отношения в семиотических системах. М., 1991. 15 с.

15. Батыршин И. 3. Лексикографические оценки правдоподобности с универсальными границами. I // Изв. РАН. Сер. Техническая кибернетика. 1994. № 5. С. 28-45.

16. Батыршин И. 3. Лексикографические оценки правдоподобности с универсальными границами. II. Операции отрицания // Изв. РАН. Сер. Теория и системы управления. 1995. № 5. С. 133-151.

17. Батыршин И. 3., Хабибуллин Р. Ф. Атрибуция псевдонимных произведений на основе инвариантных реляционных алгоритмов кластеризации // Труды Международного семинара по компьютерной лингвистике и ее приложениям. Казань, 1995. С. 43-51.

18. Безусяк Ю. А. Проблема создания и внедрения экспертных систем искусственного интеллекта. Киев, 1990. 20 с.

19. Беллман Р. Введение в теорию матриц. М.: Наука, Гл. редакция физико-математической литературы, 1969. 368 с.

20. Бернштейн А. С., Коровин С. Я., Мелихов А. Н., Сергеев Н. Е. Функционально-структурное исследование ситуационно-фреймовой сети экспертной системы с нечеткой логикой // Теоретическая кибернетика. 1994. Т. 2. С. 71-83.

21. Биркгоф Г. Теория решеток. М.: Наука, 1984. 566 с.

22. Блишун А. Ф. Нечеткие индуктивные модели обучения в экспертных системах // Изв. АН СССР. Сер. Техническая кибернетика. 1990. Т. 5. С. 90-104.

23. Блишун А. Ф., Знатков С. Ю. Обоснование операций теории нечетких множеств // Нетрадиционные модели и системы с нечеткими знаниями / Под ред. А. Ф. Влишуна. М.: Энергоатомиздат, 1991. С. 21-33.

24. Борисов А. Н., Глушков В. И. Использование нечеткой информации в экспертных системах // Новости искусственного интеллекта. 1991. Т. 3. С. 13—41.

25. Боровков А. А. Теория вероятностей. М.: Наука, 1986. 432 с.

26. Владимиров Д. А. Булевы алгебры. СПб.: Изд-во СПбГУ, 2000.

27. Гавурин М. К., Малоземов В. Н. Экстремальные задачи с линейными ограничениями: учебное пособие. Л.: ЛГУ, 1984. 175 с.

28. Горбатов В. А., Огиренко А. Г., Смирнов М. И. Искусственный интеллект в САПР. М., 1994. 184 с.

29. Городецкий В. И. Прикладная алгебра и дискретная математика. Ч. 1. Алгебраические системы. Л.: МО СССР, 1984. 174 с.

30. Городецкий В. И. Прикладная алгебра и дискретная математика. Ч. 2. Формальные системы нелогического типа. Л.: МО СССР, 1986. 200 с.

31. Городецкий В, И. Прикладная алгебра и дискретная математика. Ч. 3. Формальные системы логического типа. Л.: МО СССР, 1987. 178 с.

32. Городецкий В. И. Алгоритмизация приближенных рассуждений на основе байесовского вывода // Труды 2-й Всесоюзной конференции «Искусственный интеллект-90». Т. 1. Минск, 1990. С. 86-92.

33. Городецкий В. И. Байесовский вывод. Препринт №149. Л.: ЛИИАН, 1991. 38 с.

34. Городецкий В. И. Адаптация в экспертных системах // Изв. РАН. Сер. Техническая кибернетика. 1993. Т. 5. С. 101-110.

35. Городецкий В. И. Алгебраические байесовские сети — новая парадигма экспертных систем // Юбилейный сборник трудов институтов Отделения информатики, вычислительной техники и автоматизации РАН. Т. 2. М.: РАН, 1993. С. 120-141.

36. Городецкий В. И. Интервальные вероятностные меры неопределенности в инженерии знаний // Теоретические основы и прикладные задачи интеллектуальных информационных технологий. СПб.: СПИИРАН, 1998. С. 44-58.

37. Городецкий В. И. Моделирование недоопределенных знаний // SCM'98. Сборник докладов. Т. 1. СПб., 1998. С. 98-102.

38. Городецкий В. И., Тулупъев А. Л. Алгебраические байесовские сети для представления и обработки знаний с неопределенностью // 4-я Санкт-Петербургская конференция «Региональная информатика-95»: Тезисы докладов, ч. 1. СПб., 1995. С. 51-52.

39. Городецкий В. И., Тулупъев А, Л. Непротиворечивость баз знаний с интервальной мерой вероятности //IV Санкт-Петербургская международная конференция «Региональная информатика-95 (РИ-95)» (Санкт-Петербург, 15-18 мая 1995 г.): Труды. СПб., 1995. С. 85-91.

40. Городецкий В. И., Тулупъев А. Л. Формирование непротиворечивых баз знаний с неопределенностью // Известия РАН. Сер. Теория и системы управления. 1997. N- 5. С. 33-42.

41. Городецкий В. И., Тулупъев А. Л. Непротиворечивость баз знаний с количественными мерами неопределенности // Шестая национальная конференция по искусственному интеллекту с международным участием КИИ'98: Труды. Т. 1. Пущино, 1998. С. 100-107.

42. Горский Д. П., Ивин А. А., Никифоров А. Л. Краткий словарь по логике. Л.: Просвещение, 1991.

43. Гукасъян Н. А., Кузнецов М. А. Состояние средств искусственного интеллекта за рубежом. Л., 1988. 57 с.

44. Дюбуа Д., Прад А. Теория возможностей. М.: Радио и связь, 1990. 290 с.

45. Еремеев А. П. О корректности модели представления знаний для экспертной системы поддержки принятия решений // Изв. РАН. Сер. Техническая кибернетика. 1993. Т. 5. С. 45-53.

46. Ершов Ю. А., Палютин Е. А. Математическая логика. М.: Наука, 1977. 336 с.

47. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. Новосибирск: Из-во Ин-та математики, 1999. 270 с.

48. Заде А. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976. 165 р.

49. Заде Л. Размытые множества и их применение в распознавании образов и кластерноманализе // Классификация и кластер. М.: Мир, 1980. С. 208-247.i

50. Захаров В. Н., Ульянов С. В. Нечеткие модели интеллектуальных промышленных регуляторов и систем управления-4 // Изв. РАН. Сер. Техническая кибернетика. 1994. Т. 5. С. 168-210.

51. Кафаров В. В., Перов В. Л., Мешалкин В. П. Принципы математического моделирования химико-технологических систем. Сер. «Химическая кибернетика. Введение в системотехнику химических производств». М.: Химия, 1974. 344 с.

52. Ковалев И. П. Представление неточности в задаче образной интерпретации объектов. Минск, 1991. 16 с.

53. Кованцов Н. И., Зражевская Г. М., Кочаровский В. Г., Михайловский В. И. Дифференциальная геометрия, топология, тензорный анализ: Сб. задач. Киев, 1989. 398 с.

54. Козелецкий Ю. Психологическая теория решений. М.: Прогресс, 1970. 504 с.

55. Косовский Н. К., Тишков А. В. Градуируемые логические значения для представления знаний // Записки научных семинаров ПОМИ. Исследования по конструктивной математике и математической логике. Вып. X. 1998. Т. 241. С. 135-149.

56. Косовский Н. К., Тишков А. В. Секвенциальное исчисление для сравнений противоречивых условий различной степени достоверности // Математические вопросы кибернетики. 1998. Т. 7. С. 213-226.

57. Косовский Н. К., Тишков А. В. Логики конечнозначных предикатов на основе неравенств. СПб.: СПбГУ, 2000. 286 с.

58. Котпенко И. В. Методы вывода в экспертных системах по неполной и противоречивой информации. СПб., 1992. 78 с.

59. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982. 432 с.

60. Крейнович В. Я., Нгуен X. Т., Городецкий В. И., Нестеров В. М., Тулупьев А. Л. Применение интервальных степеней доверия: аналитический обзор // Информационные технологии и интеллектуальные методы. СПб.: СПИИРАН, 1999. Т. 3. С. 6-61.

61. Ларичев О. И. и др. Новые возможности компьютерного обучения // Вестник РАН. 1989. Т. 69, № 2. С. 106-109.

62. Левин Р., Дранг Д., Эделъсон Б. Практическое введение в технологию искусственного интеллекта и экспертных систем с иллюстрациями на Бейсике. М.: Финансы и статистика, 1990. 240 с.

63. Лобацевич А. В., Тулупъев А. Л. Использование методологии машинного обучения для создания интеллектуальных посредников // Международная конференция «Эволюция инфосферы-95»: Тезисы. М., 1995.

64. Лобацевич А. В., Тулупъев А. Л. Классификация текстовой информации с использованием индуктивного обучения и аппарата алгебраических байесовских сетей // Информационные технологии и интеллектуальные методы. СПб.: СПИИРАН, 1996. С. 120-124.

65. Логика и компьютер. М.: Наука, 1990. 240 с.

66. Марселлус Д. Программирование экспертных систем на Турбо Прологе. М.: Финансы и статистика, 1994. 256 с.

67. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971. 320 с.

68. Микони С. В. Теория и практика рационального выбора. М.: Маршрут, 2004. 463 с.

69. Наринъяни А. С. Недоопределенные модели и операции с недоопределенными значениями. Новосибирск, 1982. 34 с.

70. Наринъяни А. С. Неопределенность в системе представления и обработки знаний // Изв. АН СССР. Сер. Техническая кибернетика. 1986. Т. 5. С. 3-28.

71. Наринъяни А. С. He-факторы и инженерия знаний: от наивной формализации к естественной прагматике // Искусственный интеллект-94. Сборник научных трудов. Рыбинск, 1994. С. 9-18.

72. Наумов Г. В., Подиновский В. В., Подиновский В. В. Субъективная вероятность: способы представления и методы получения // Изв. АН СССР. Сер. Техническая кибернетика. 1991. Т. 5. С. 94-109.

73. Нгуен М. X. Моделирование приближенных рассуждений с помощью нечеткозначной вероятностной логики // Изв. РАН. Сер. Техническая кибернетика. 1993. Т. 5. С. 94100.

74. Нейлор К. Как построить свою экспертную систему. М.: Энергоатомиздат, 1991. 288 с.

75. Никитин Д. А., Тулупъев А. Л., Ромашова М. Н. Вычисление согласованных оценок истинности в вероятностных и нечетких фрагментах знаний // Труды СПИИРАН. Вып. 1. 2002. Т. 1. С. 241-246.

76. Николенко С. И., Тулупъев А. Л. Простейшие циклы в байесовских сетях доверия: распределение вероятностей и возможность его непротиворечивого задания // Труды СПИИРАН. 2005. Вып. 2. СПб.: Наука, 2004. Т. 1. С. 119-126.

77. Николенко С. И., Тулупъев А. А. Вероятностная семантика байесовских сетей в случае линейной цепочки фрагментов знаний // Труды СПИИРАН. Вып. 2. СПб.: Наука, 2005. Т. 2. С. 53-75.

78. Николенко С. И., Тулупъев А. Л. Разворот ребер как метод работы с направленными циклами в байесовских сетях // Научная сессия МИФИ-2005. Сборник научныхтрудов. В 15 томах. Т. 3. 2005. С. 176-178.

79. Николенко С. И., Тулупъев А. А. Самообучающиеся системы. М.: МЦНМО, 2009. 288 с.

80. Орловский С. А. Проблемы принятия решений, при нечеткой исходной информации. М.: Наука, 1981. 208 с.

81. Осипов Г. С. Приобретение знаний интеллектуальными системами: Основы теории и технологии. М .: Физматлит, 1997. 112 с.

82. Петприна А. М. Экспертные системы в робототехнике. М.: ВИНИТИ, 1992. 183 с.

83. Попов Э. В. Экспертные системы. М.: Наука, 1987. 284 с.

84. Поспелов Д. А. Моделирование рассуждений. М.: Радио и связь, 1989. 184 с.

85. Романов А. А., Шемякин Ю. И. Индуктивно-дедуктивный логический вывод в нечетких условиях // Изв. РАН. Сер. Техническая кибернетика. 1992. Т. 5. С. 63-68.

86. Рябинин И. А. Надежность и безопасность структурно-сложных систем. СПб.: Политехника, 2000. 248 с.

87. Саати Т. Принятие решений. Метод анализа иерархий. М.: Радио и связь, 1993. 316 с.

88. Самородницкий А. А. Теория меры. Л.: ЛГУ, 1990. 340 с.

89. Сироткин А. В. Байесовские сети доверия: дерево сочленений и его вероятностная семантика // Труды СПИИРАН. Вып. 3. Т. 1. СПб., 2006. С. 228-239.

90. Сиротпкин А. В., Тулупъев А. Л. Локальный априорный вывод в алгебраических байесовских сетях: комплекс основных алгоритмов // Труды СПИИРАН. Вып. 5. СПб.: Наука, 2007. С. 100-111.

91. Сиротпкин А. В., Тулупъев А. Л. Структура байесовской сети доверия для моделирования и обработки результатов теста последовательных разведений // Научная конференция МИФИ. 2007. Материалы. Т. 3. М.: МИФИ, 2007. С. 106-109.

92. Сироткин А. В., Тулупьев А. Л. Матричные уравнения локального логико-вероятностного вывода в алгебраических байесовских сетях // Труды СПИИРАН. 2008. Вып. 6. СПб.: Наука, 2008. С. 131-149.

93. Сироткин А. В., Тулупьев А. Л., Николенко С. И. Устойчивость и множественная устойчивость глобальной непротиворечивости алгебраических байесовских сетей // Труды СПИИРАН. Вып. 2. СПб.: Наука, 2005. Т. 2. С. 86-93.

94. Сироткин А. В., Тулупьев А. Л., Николенко С. И. Устойчивость непротиворечивости алгебраических байесовских сетей // Конференция f «Мягкие вычисления и измерения», г. Санкт-Петербург: Труды. СПб., 2005. С. 101-110.

95. Сироткин А. В., Тулупьев А. Л., Николенко С. И. Генетические алгоритмы и алгебраические байесовские сети: моделирование отбора под действием неблагоприятных факторов // Научная сессия МИФИ-2006. Сборник научных трудов. Т. 3. М., 2006. С. 178-179.

96. Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990. 440 с.

97. Тулупъев А. А. Алгебраические байесовские сети: теоретические основы и непротиворечивость. СПб.: СПИИРАН, 1995. 76 с.

98. Тулупъев А. А. Непротиворечивость знаний с неопределенностью и вывод на них // Всероссийская научно-техническая конференция «Электроника и информатика»: Тезисы. М., 1995. С. 309-310.

99. Тулупъев А. Л. Эволюция моделей неопределенности // Международная конференция «Эволюция инфосферы-95»: Тезисы. М., 1995.

100. Тулупъев А. Л. Алгебраические байесовские сети для представления и обработки знаний с неопределенностью. Диссертация на соискание ученой степени кандидата физико-математических наук. СПб., 1996. 260 с.

101. Тулупъев А. Л. Композиция распределений случайных бинарных последовательностей // Информационные технологии и интеллектуальные методы. СПб.: СПИИРАН, 1996. С. 105-112.

102. Тулупъев А. Л. Структуры вероятностей на пропозициональных формулах // Информационные технологии и интеллектуальные методы: Сб. трудов СПИИРАН. 1997. Вып. 1. СПб.: СПИИРАН, 1996. С. 61-71.

103. Тулупъев А. Л. Байесовские сети доверия и алгебраические байесовские сети: сравнительный анализ выразительной мощности // Информационные технологии и интеллектуальные методы: Сб. трудов СПИИРАН. 1997. Вып. 2. СПб.: СПИИРАН, 1997. С. 121-147.

104. Тулупъев А. Л. Поддержание непротиворечивости фрагментов знаний с интервальной нечеткой мерой неопределенности // Теоретические основы и прикладные задачи интеллектуальных информационных технологий. СПб.: СПИИРАН, 1998. С. 82-92.

105. Тулупъев А. Л. Поддержание непротиворечивости фрагментов знаний с оценками доверия и правдоподобия // Информационные технологии и интеллектуальные методы: Сб. трудов СПИИРАН. 1999. Вып. 3. СПб.: СПИИРАН, 1999. С. 72-97.

106. Тулупъев А. Л. Алгебраические байесовские сети: логико-вероятностный подход к моделированию баз знаний с неопределенностью. СПб.: СПИИРАН, 2000. 282 с.

107. Тулупъев А. Л. Метод построения и исследования баз фрагментов знаний с неопределенностью // Труды СПИИРАН. Вып. 1. 2002. Т. 1. С. 258-271.

108. Тулупъев А. Л. Семантика моделей баз фрагментов знаний с неопределенностью // Телекоммуникации, математика и информатика — исследования и инновации. Вып. 6. Межвузовский сборник научных трудов. СПб.: ЛГОУ им. А. С. Пушкина, 2002. С. 178— 180.

109. Тулупъев А. Л. Устойчивость вывода оценок надежности в базах фрагментов знаний // Научная сессия МИФИ-2002. Сборник научных трудов. Т. 3. 2002. С. 135.

110. Тулупъев А. Л. Генерация множества ограничений на распределение оценок вероятности над идеалом цепочек конъюнкций // Вестник молодых ученых. 2004. К2 4. Сер. Прикладная математика и механика. 2004. № 1. С. 35-43.

111. Тулупъев А. Л. Ациклические алгебраические байесовские сети: логико-вероятностный вывод // Нечеткие системы и мягкие вычисления: Научный журнал Российской ассоциации нечетких систем и мягких вычислений. 2006. Т. 1, К5 1. С. 57-93.

112. Тулупъев А. А. Дерево смежности с идеалами конъюнктов как ациклическая алгебраическая байесовская сеть // Труды СПИИРАН. Вып. 3. Т. 1. СПб., 2006. С. 198-227.

113. Тулупъев А. Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. Элементы мягких вычислений. СПб.: СПб-ГУ; ООО Издательство «Анатолия», 2007. 40 с.

114. Тулупъев А. Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. Элементы мягких вычислений. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. 80 с.

115. Тулупъев А. Л. Байесовские сети доверия: непротиворечивость направленного циклического паттерна // Международная конференция по мягким вычислениям и измерениям. Сборник докладов. 2007. Т. 1. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2007. С. 212-215.

116. Тулупъев А. Л. Непротиворечивость семантического образа направленного цикла в байесовской сети доверия // X Санкт-Петербургская международная конференция «Региональная информатика-2006 (РИ-2006)»: Труды. СПб., 2007. С. 125-131.

117. Тулупъев А.Л. Байесовские сети: логико-вероятностный вывод в циклах. СПб.: Изд-во С.-Петербургского ун-та, 2008. 140 с.

118. Тулупъев А. Л. Задача локального автоматического обучения в алгебраических байесовских сетях: логико-вероятностный подход j j Труды СПИИРАН. 2008. Т. 7. С. 11-25.

119. Тулупъев А. Л. Алгебраические байесовские сети: реализация логико-вероятностного вывода в комплексе java-nporpaMM // Труды СПИИРАН. 2009. Вып. 8. 2009. С. 191-232.

120. Тулупъев А. Л. Алгебраические байесовские сети: система операций локального логико-вероятностного вывода // Информационно-измерительные и управляющие системы. 2009. № 4. С. 41-44.

121. Тулупъев А. Л. Непротиворечивость оценок вероятностей в алгебраических байесовских сетях // Вестник СПбГУ. Сер. 10. 2009. № 3. С. 144-151.

122. Тулупъев А. Л. Непротиворечивость оценок вероятностей в идеалах конъюнктов и дизъюнктов // Вестник СПбГУ. Сер. 10. 2009. № 2. С. 121-131.

123. Тулупъев А. Л. Преобразование ациклических байесовских сетей доверия в алгебраические байесовские сети // Известия высших учебных заведений: Приборостроение. 2009. № 3. С. 21-23.

124. Тулупъев А. Л. Согласованность данных и оценка вероятности альтернатив в цикле стохастических предпочтений // Известия высших учебных заведений: Приборостроение. 2009. Ш 7. С. 3-7.

125. Тулупъев А. Л., Абрамян А. К. Логико-вероятностный вывод в направленном БСД-цикле // Труды СПИИРАН. Т. 4. СПб.: Наука, 2007. С. 87-118.

126. Тулупъев А. Л., Городецкий В. И. Алгебраические байесовские сети: поддержание непротиворечивости баз знаний // Международная конференция «Знания — Диалог — Решение» (KDS-95): Доклады. Ялта, 1995. С. 151-159.

127. Тулупъев А. Л., Никитин Д. А. Экстремальные задачи в апостериорном выводе над идеалами цепочек конъюнкций // Труды СПИИРАН. 2005. Вып. 2. СПб.: Наука, 2005. Т. 2. С. 12-52.

128. Тулупъев А. Л., Николенко С. И. Циклы обратной связи узлов с одним предшественником в байесовских сетях доверия. Труды IX конференции «Региональная информатика», Санкт-Петербург, 2004. 65-66 с.

129. Тулупьев А. Л., Николенко С. И., Никитин Д. А., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: детерминированный вариант // Известия высших учебных заведений: Приборостроение. 2006. № 11. С. 35-39.

130. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 608 с.

131. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: стохастический вариант // Известия высших учебных заведений: Приборостроение. 2006. № 11. С. 39-44.

132. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах / / Известия высших учебных заведений: Приборостроение. 2006. № 7. С. 20-26.

133. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Циклы в байесовских сетях: вероятностная семантика и отношения с соседними узлами // Труды СПИИРАН. Вып. 3. Т. 1. СПб., 2006. С. 240-263.

134. Тулупьев А. Л., Сироткин А. В. Алгебраические байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. Т. 6, № 10. С. 85-87.

135. Тулупъев А. Л., Сиротпкин А. В., Николенко С. И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петербургского ун-та, 2009. 400 с.

136. Тулупъев А. Л., Столяров Д. М., Ментюков М. В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях / / Труды СПИИРАН. Вып. 5. СПб.: Наука, 2007. С. 71-99.

137. Уотперман Д. Руководство по экспертным системам. М.: Мир, 1989. 390 с.

138. Уткин Л. В. Анализ риска и принятие решений при неполной информации. СПб.: Наука, 2007. 404 с.

139. Уэно X., Исидэука М. Представление и использование знаний. М.: Мир, 1989. 222 с.

140. Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, 1984.

141. Финн В. К. Правдоподобные рассуждения в экспертных системах с неполной информацией: Автореферат диссертации на соискание ученой степени доктора технических наук. М., 1990. 62 с.

142. Хачатрян А. Р. Анализ классических методов объединения свидетельств в экспертных системах // Изв. АН СССР. Сер. Техническая кибернетика. 1988. Т. 2. С. 135-144.

143. Хачатрян А. Р. Неточный вывод на знаниях // Искусственный интеллект. Справочник. Т. 2. / Под ред. Д. Поспелова. М.: Радио и связь, 1990. С. 105-109.

144. Хачиян Л. Г. Полиномиальный алгоритм в линейном программировании // Доклады АН СССР. 1979. Т. 244. С. 1093-1096.

145. Хованов Н. В. Анализ и синтез показателей при информационном дефиците. СПб.: Издательство С.-Петербургского университета, 1996. 196 с.

146. Черемхин М. К. Экспертные системы. М.: МГОУ, 1994. 78 с.

147. Ширяев А. Н. Вероятность. М.: Наука, 1989. 640 с.

148. Экспертные системы. Принципы работы и примеры / Под ред. Р. Форсайта. М.: Радио и связь, 1987. 224 с.

149. Элти Д., Кумбс М. Экспертные системы: концепции и примеры. М.: Финансы и статистика, 1987. 192 с.

150. Яковлев Е. А. Одобрена концепция «Руководства по выражению неопределенности измерения» и принят план мероприятий по его внедрению в отечественную метрологическую практику // Законодательная и прикладная метрология. 2000. № 3. С. 54-57.

151. Abadi М., Halpern J. Y. Decidability and Expressiveness for First-Order Logics of Probability // Artificial Intelligence. 1990. Vol. 46. P. 311-350.

152. Aji S., Horn G., McEliece R. The convergence of iterative decoding on graphs with a single cycle // Proc. CISS 1998. Princeton, 1998. P. 423-434. *

153. Allison P. D. Missing Data / Sage University Paper Series on Quantitative Applications in the Social Sciences, 07-136 / Ed. by M. S. Lewis-Beck. Thousand Oaks, London, New Delhi: Sage Publications, 2001. 93 p.

154. Anderson J. R. Cognitive Psychology and Its Implications. N.Y.: W. H. Freeman, 1980.

155. Artificial Intelligence and Expert Systems / Ed. by S. E. Savory. N.Y.: J. Wiley & Sons Ltd, 1988. 278 p.

156. Artificial Intelligence in Design'94 / Ed. by J. S. Gero, F. Sudweeks. London: Kluwer Acad. Publ., 1994. 766 p.

157. Atanassov К. T. Intuitionistic fuzzy sets // Fuzzy Sets and Systems. 1986. Vol. 20, N. 1. P. 87-96.

158. Atanassov К. T. Review and new results on intuitionistic fuzzy sets // Preprint IM-MFAIS-1-88. 1988.

159. Atanassov К. T. More on intuitionistic fuzzy sets // Fuzzy Sets and Systems. 1989. Vol. 33, N. 1. P. 37-45.

160. Atanassov К. Т. Operations over interval valued intuitionistic fuzzy sets // Fuzzy Sets and Systems. 1994. Vol. 64. P. 159-174.

161. Atanassov К. Т., Gargov G. Interval valued intuitionistic fuzzy sets // Fuzzy Sets and Systems. 1989. Vol. 31, N. 3. P. 343-349.

162. Atanassov К. Т., Nikolov N., Kirova Z., Nikolova N. On the modelling of industrial chemical processes by intuitionistic fuzzy generalized nets // Notes on Intuitionistic Fuzzy Sets. 1996. Vol. 2, N. 2. P. 16-20.

163. Bacchus F. A Logic for Statistical Information // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 5). 1990. Vol. 19. P. 3-14.

164. Bacchus F. Lp, a logic for representing and reasoning with statistical knowledge // Computational Intelligence. 1990. Vol. 6. P. 209-231.

165. Bacchus F. On Probability Distributions Over Possible Worlds // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 4). 1990. Vol. 9. P. 217-226.

166. Bacchus F., Dalmao S., Pitassi T. Algorithms and Complexity Results for #SAT and Bayesian Inference 11 FOCS 2003. 2002. P. 340-351.

167. Baldwin J. F. et al. Fril — Fuzzy and Evidential Reasoning in Artificial Intelligence. N.Y.: Research Studies Press, Wiley, 1995. 141 p.

168. Berry A., Bordat J., Heggernes P., Simonet G., Villanger Y. A wide-range algorithm for minimal triangulation from an arbitrary ordering: Tech. Rep. 243: University of Bergen, Norway, Department of Informatics, 2003.

169. Bhatnagar R. K., Kanal L. N. Handling Uncertain Information: A Review of Numeric & Non-Numeric Methods // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 3-26.

170. Biazzo V., Gilio A., Lukasiewicz Т., Sanfilippo G. Probabilistic Logic under Coherence: Complexity and Algorithms // ISIPTA. 2001. P. 51-61.

171. Biazzo V., Gilio A., Lukasiewicz Т., Sanfilippo G. Probabilistic Logic under Coherence, Model-Theoretic Probabilistic Logic, and Default Reasoning // ECSQARU. 2001. P. 290302.

172. Bondy J. A., Murty J. S. R. Graph Theory with Applications. New York: Elsevier Science Publishing Co., 1976. 264 p.

173. Bonisson P. P., Decker K. S. Selecting Uncertainty Calculi and Granularity // Machine Intelligence 8z Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 217-247.

174. Bonissone P. P., Tong R. M. Reasoning with Uncertainty in Expert Systems // International Journal of Man-Machine Studies. 1985. Vol. 22. P. 241-250.

175. Boole G. An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities. Cambridge: Macmillan/London: Walton & Maberly, 1854.

176. Bouchon В., Despres S. Propagation of Uncertanities and Inaccuracies in Knowledge-Based Systems // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 58-65.

177. Buehrer D. J. From interval probability theory to computable fuzzy first-order logic and beyond // Proceedings of the Third IEEE Conference on Fuzzy Systems (Orlando, FL, June 26-29, 1994). Vol. II. 1994. P. 1428-1433.

178. Bundy A. Incidence Calculus: A Mechanism for Probabilistic Reasoning // Proceedings of the International Conference on Fifth Generation Computer Systems 1984, Tokyo, Japan. 1984. P. 166-174.

179. Bundy A. Incidence Calculus: A Mechanism for Probabilistic Reasoning // Journal of Automated Reasoning. 1985. Vol. 1, N. 3. P. 263-283.

180. Bundy A. Correctness Criteria of Some Algorithms for Uncertain Reasoning Using Incidence Calculus // Journal of Automated Reasoning. 1986. Vol. 2, N. 2. P. 109-126.

181. Carnap R. The two concepts of probability // Logical Foundations of Probability. University of Chicago Press, Chicago, 1950. P. 19-51.

182. Carnap R. Decision Making // Studies in Inductive Logic and Probability / Ed. by R. Car-nap, R. Jeffrey. University of California Press, Berkeley, 1971. Vol. 1. P. 7-9.

183. Castillo E., Gutierrez J. M., Hadi A. S. Modeling Probabilistic Networks of Discrete and Continuous Variables // Journal of Multivariate Analysis. 1998. Vol. 64. P. 48-65.

184. Chandru V., Hooker J. Optimization Methods for Logical Inference. N.Y.: Wiley, 1999.

185. Charnes A., Cooper W. W. Programming with Linear Fractional Functionals // Naval Research Logistics Quarterly. 1962. Vol. 9. P. 181-186.

186. Chau С. W. R., Lingras P., Wong S. К. M. Upper and Lower Entropies of Belief Functions Using Compatible Probability Function '// Methodologies for Intelligent Systems / Ed. by J. Komorowski, Z. W. Ras. Berlin: Springer-Verlag, 1993. P. 306-315.

187. Chee L. Computing the Value of a Boolean expression with intervals is NP-hard. Master's thesis, Computer Science Dept., Univ. of Texas at El Paso, 1996.

188. Chee L. Computing the Value of a Boolean expression with intervals is NP-hard // Reliable Computing. 1997. Vol. 3, N. 2. P. 155-172.

189. Cheesman P. Probabilistic vs. Fuzzy Reasoning // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P.' 85-102.

190. Cooper G. F. The Computational Complexity of Probabilistic Inference using Bayesian Belief Networks // Artificial Intelligence. 1990. Vol. 42. P. 393-405.

191. Corlett A. G., Todd S. J. A Monte-Carlo Approach to Uncertain Inference // Artificial Intelligence and ita Applications. / Ed. by R. A. Cohn, J. R. Thomas. N.Y.: J. Wiley & Sons Ltd, 1986. P. 127-137.

192. Cortes-Rello E., Golsham F. Management of Uncertainty for Intelligent Financial Systems // Proc. of 1st-International Conference on AI Applications oni Wall Street. N.Y., 1991. P. 238-243.

193. Cowell R. G., Dawid A. P., Lauritzen S. L., Spiegelhalter D. J. Probabilistic Networks and Expert Systems. Springer-Verlag, 1999.

194. Cravo M. R., Martins J. R. A Unified Approach to Default Reasoning and Belief Revision // Lectures Notes in Computer Science. 1993. Vol. 727. P. 226-241.

195. Сиг W., Blockley D. I. Interval probability theory of evidential support // International Journal of Intelligent Systems. 1990. Vol. 5. P. 183-192.253. da Silva F. S. C. On the Relations Between Incidence Calculus and Fagin-Halpern Structures.

196. Dagum P., Luby M. Approximating probabilistic inference in Bayesian belief netowrks is NP-hard 11 Artificial Intelligence. 1993. Vol. 60. P. 141-153.

197. Dan Q., Dudeck J. Some Problems Related with Probabilistic Interpetations for Certainity Factors // Proc. of 5th Annual IEEE Symposium on Computer-Based Medical Systems. Washington, 1992. P. 538-545.

198. Dantzig G. B. Maximization of a linear function of variables subject to linear inequalities // Activity Analysis of Production and Allocation. N.Y.: Wiley, 1951. P. 339-347.

199. Darwiche A. A Differential Approach to Inference in Bayesian Networks // Journal of the ACM. 2003. Vol. 50, N. 3. P. 280-305.

200. Darzentas I. Knowledge-Modelling in Fuzzy Expert Systems // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 159-172.

201. De Finetti B. Sul significato soggettivo della probability. // Pundamenta Mathematicae. 1931. Vol. 17. P. 298-329.

202. De Finetti B. Theory of Probability. N.Y.: J. Wiley & Sons, 1974.

203. Dechter Ft., Rish I. Mini-Buckets: A General Scheme for Bounded Inference // Journal of the ACM. 2003. Vol. 50, N. 2. P. 107-153.

204. Driankov D. A Calculus for Belief Intervals Representation of Uncertainty // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag,1987. P. 205-216.

205. Dubois D., Fargier H., Prade H., PerN.Y. P. Quantitative Decision Theory: From Savage's Axioms to Nonmonotonic Reasoning // Journal of the ACM. 2002. Vol. 49, N. 4. P. 445-495.

206. Dubois D., Prade H. Fuzzy Sets and Systems: Theory and Applications. N.Y., London: Academic Press, 1980.

207. Dubois D., Prade H. The principle of Minimum Specifity as a Basis for Evidentional Reasoning // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 75-84.

208. Dubois D., Prade H. Conditioning in Possibility and Evidence Theory // Uncertainty and Intelligent Systems / Ed. by B. Bouchon, L. Saitfa, R. R. Yager. Berlin: Springer-Verlag,1988. P. 401-408.

209. Dubois D., Prade H. Modeling Uncertain and Vague Knowledge in Possibility and Evidence Theories // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 4). 1990. Vol. 9. P. 303-318.

210. Dubois D., Prade H. Epistemic Entrenchment and Possibilistic Logic // Artificial Intelligence. 1991. Vol. 50. P. 223-239.

211. Dubois D., Sandri S. A., Kalfsbeek H.~ W. Corrections to "Eliciation, Assessment, and Pooling of Expert Judgements Using Possibility Theory" // IEEE Transactions on Fuzzy Systems. 1995. Vol. 3, N. 4. P. 479.

212. Dubois D., Sandri S. A., Kalfsbeek H. W. Eliciation, Assessment, and Pooling of Expert Judgements Using Possibility Theory // IEEE Transactions on Fuzzy Systems. 1995. Vol. 3, N. 3. P. 313-335.

213. Edwards W. Comparing Approaches to Uncertain Reasoning // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 5). 1990. Vol. 10. P. 128-137.

214. Enderton H. B. A Mathematical Introduction to Logic. N.Y.: Academic Press, 1972.

215. Fagin R., Halpern J. Y. Uncertainty, Belief, and Probability // Computational Intelligence. 1991. Vol. 6. P. 160-173.

216. Fagin R., Halpern J. Y. Uncertainty, Belief, and Probability-2 // Proc. of the IEEE Symposium on Logic and Computer Science. 1991. Vol. 7. P. 160-173.

217. Fagin R., Halpern J. Y. Reasoning about Knowledge and Probability // Journal of the Association for Computing Machinery. 1994. Vol. 41, N. 2. P. 340-367.

218. Fagin R., Halpern J. Y., Megiddo N. A Logic for Reasoning about Probabilities // Report RJ 6190(60900) 4/12/88. 1988. P. 1-41.

219. Fagin R., Halpern J. Y., Megiddo N. A Logic for Reasoning about Probabilities // Information and Computation. 1990. Vol. 87, N. 1/2. P. 78-128.

220. Farkas G. A Fourier-fele mechanikai elv alkalmazasai // Mathematikai es TermeszettudomaN.Y.i Ertesito. 1894. Vol. 12. P. 457-472.

221. Flores M. J., Gamez J. A. Triangulation of Bayesian networks by retriangulation j j International Journal of Intelligent Systems. 2003. Vol. 18, N. 2. P. 153-164.

222. Fourier J. B. J. Analyse des travaux de l'Academie Royale des Sciences, pendant l'annee 1823, Partie mathematique // Histoire de l'Academie Royale de Sciences de l'lnstitut de France. 1826. Vol. 6.

223. Fox J. Three Arguments for Extending the Framework of Probability // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 447-458.

224. Friedman N., Halpern J. Y. Plausibility Measures and Default Reasoning // Journal of the ACM. 2001. Vol. 48, N. 4. P. 648-685.

225. Frisch A. M., Haddawy P. Anytime Deduction for Probabilistic Logic // Artificial Intelligence. 1994. Vol. 69. P. 93-112.

226. Fua P. V. Using Probability Density Functions in the Framework of Evidentional Reasoning // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 101-110.

227. Fuzzy Logic in Artificial Intelligence / Ed. by E. P. Klement, W. SlaN.Y. Berlin: Springer-Verlag, 1993. 192 p.

228. Fuzzy Logic: State of the Art / Ed. by R. Lowen, M. Roubens. London: Kluwer Acad. Publ., 1993. 588 p.

229. Fuzzy Reasoning in Information, Decision and Control Systems / Ed. by S. G. Tzafestas, A. Venetsanopoulos. London: Kluwer Acad. Publ., 1993. 568 p.

230. Gader P., Keller J. M., Cai J. A Fuzzy Logic System for the Detection and Recognition of Hand-Written Street Numbers // IEEE Transactions on Fuzzy Systems. 1995. Vol. 3, N. 1. P. 83-95.

231. Gaines В. R. Structure, Development, and Applications of Expert Systems in Integrated Manufacturing // Artificial Intelligence Implications for CIM / Ed. by A. Kusiak. Berlin: Springer-Verlag, 1988. P. 117-161.

232. Gargov G. K., Atanassov К. T. Two results in intuitionistic fuzzy logic // C. R. Acad. Bulgare Sci. 1992. Vol. 45, N. 12. P. 29-31.

233. Gartbba S. F. Evidence Aggregation in Expert Judgements // Uncertainty and Intelligent Systems / Ed. by B. Bouchon, L. Saitfa, R. R. Yager. Berlin: Springer-Verlag, 1988. P. 385400.

234. Gau W.-L., Buehrer D. J. Vague sets // IEEE Transactions on Systems, Man, and Cybernetics. 1993. Vol. 23, N. 2. P. 610-614.

235. Gerla G. Inference in Probability Logic // Artificial Intelligence. 1994. Vol. 70. P. 33-52.

236. Good I. J. Subjective probability as the measure of a non-measurable set // Logic, Methodology and Philosophy of Science / Ed. by E. Nagel, P. Suppes, A. Tarski. Stanford University Press, Stanford, 1962. P. 319-329.

237. Gorodetsky V. I. Bayes Inference and Decision Making in Artificial Intelligence Systems // Industrial Applications of Artificial Intelligence. Amsterdam: Elsevier Science Publishers B. V., 1991. P. 276-281.

238. Gorodetsky V. I. Adaptation Problems in Expert Systems // International Journal of Adaptive Controle and Signal Processing. 1992. Vol. 6. P. 201-209.

239. Gorodetsky V. I. New Architecture of Expert System Tool and Its Agriculture Implementation Possibility // Proc. of IFAC Workshop on Expert Systems in Agriculture. Huangsham, China, August 12-14, 1992. International Academia Publ., 1992. P. 41-47.

240. Groothuizen R. J. Inexact Reasoning in Expert Systems: an Integrating Overview // National Aerospace Laboratory, NLR Report No NLR TR 86009 U, January 1986. 391-406. P. 1986.

241. Grosof В. N. Evidential Confirmation as Transformed Probability // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 153-166.

242. Grosof B. N. An Inequality Paradigm for Probabilistic Knowledge. (The Logic of Conditional Probability Intervals) // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 259-275.

243. Guan J. W., Bell D. A. Improving Shafer-Logan's Algorithm for Handling Hierarchical Evidence // Database and Expert Systems Applications / Ed. by V. Marfk, J. Lazansky, R. R. Wagner. Berlin: Springer-Verlag, 1993. R 413-423.

244. Gupta A., E. P. D. Principles of Expert Systems. N.Y.: IEEE, 1988. 450 p.

245. Hagen B. W. Bi-Directional Probabilistic Assessment // Industrial and Engineering Applications of Artificial Intelligence and Expert-Systems / Ed. by P. Belli, P. I. Radermacher. Berlin: Springer-Verlag, 1992. P. 566-571.

246. Halfin S. The sphere method and the robustness of the ellipsoid algorithm // Mathematical Programming. 1983. Vol. 26. P. 109-116.

247. Halpern J. Y. Using reasoning about knowledge to analyze distributed systems // Annual Review of Computer Science / Ed. by J. F. Traub, B. J. Grosz, B. W. Lampson, N. J. Nilsson. Annual Reviews Inc., Palo Alto, Calif., 1987. Vol. 2. P. 37-68.

248. Halpern J. Y. An Analysis of First-Order Logics of Probability // Artificial Intelligence. 1990. Vol. 46. P. 311-350.

249. Halpern J. Y. Reasoning about uncertainty. Cambridge, MA: MIT Press, 2003.

250. Halpern J. Y., van der Meyden R., Vardi M. Y. Complete Axiomatizations for Reasoning about Knowledge and Time // SIAM Journal of Computing. 2003. Vol. 33, N. 3. P. 674-703.

251. Hanks S., McDermott D. Modelling a Dynamic and Uncertain World-1 // Artificial Intelligence. 1994. Vol. 66. P. 1-55.

252. Heckerman D. Probabilistic Interpretations for MYCIN'S Certainty Factors // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 167-196.

253. Heckerman D., Chickering D., Meek C., Rounthwaite R., Kadie C. Dependency Networks for Density Estimation, Collaborative Filtering, and Data Visualization // Journal of Machine Learning Research. 2000. Vol. I. P. 49-75.

254. Horvitz E., Heckerman D. The Inconsistent Use of Measures of Certainty in Artificial Intelligence Research // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 137-152.

255. Hsia Y.-T. Characterizing Belief witn Minimum Commitment // Proc. of 12th International Joint Conference on Artificial Intelligence. Sydney: Morgan Kaufmann Publ., 1991. P. 11841189.

256. Hulten G., , Chickering D., Heckerman D. Learning Bayesian Networks from Dependency Networks: A Preliminary Study // Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics. 2003.

257. Ip Н. Н. S., Wong Н.-М. Evidentional Reasoning in Foreign Exchange Rates Forecasting // Proc. of 1st International Conferenceon AI Applications on Wall Street. N.Y., 1991. P. 152158.

258. Jaffray J.-Y. Application of Linear Utility Theory to Belief Functions // Uncertainty and Intelligent Systems / Ed. by B. Bouchon, L. Saitfa, R. R. Yager. Berlin: Springer-Verlag, 1988. P. 1-8.

259. Jen J. A Framework of Fuzzy Evidentional.Reasoning // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 4). 1990. Vol. 9. P. 227-239.

260. Jensen C. S., Kong A., KjcBrulff U. Blocking-Gibbs sampling in very large probabilistic expert systems // International Journal of Human-Computer Studies. 1995. Vol. 42. P. 647666.

261. Jensen F. V. Bayesian Networks and Decision Graphs. Springer-Verlag, 2002.

262. Johnson J. A., Smartt H. B. Advantages,of an Alternative Form of Fuzzy Logic // IEEE Transactions on Fuzzy Systems. 1995. Vol. 3, N. 2. P. 149-157.

263. Kane Т. B. Maximum Entropy in Nilsson's Probabilistic Logic // Proc. of 11th International Joint Conference on Artificial Intelligence. Detroit: Morgan Kaufmann Publ., 1989. P. 452-457.

264. Kasprzyk J., Fednzzi M. Inference via Belief Qualified IF-THEN Rules Based on Cam-patibility Relations and Possibility Theory // Uncertainty and Intelligent Systems / Ed. by B. Bouchon, L. Saitfa, R. R. Yager. Berlin: Springer-Verlag, 1988. P. 25-32.

265. Kaufman C., Perlman R., Speciner M. Network Security: Private Communication in a Public,World. N.Y.: Prentice Hall PTR, 2002. 670 p.

266. Keynes J. M. A Treatise on Probability. Macmillan, London, 1921.

267. Kim S. Checking a Rule Base with Certainty Factor for Incompleteness and Inconsistency // Uncertainty and Intelligent Systems / Ed. by B. Bouchon, L. Saitfa, R. R. Yager. Berlin: Springer-Verlag, 1988. P. 201-208.

268. Kindermann R., Snell J. L. Markov Random Fields and Their Applications. American Mathematical Society, 1980. 142 p.

269. Kleindorfer P. R., Kunreuther H. C., Schoemaker P. J. H. Decision sciences. An integrative perspective. Cambridge: Cambridge University Press, 1993.

270. Knowledge, Skill, and Artificial Intelligence / Ed. by B. Goranzon, I. Josefson. Berlin: Springer-Verlag, 1988. 193 p.

271. Korb К. В., Nicholson A. E. Bayesian Artificial Intelligence. Boca Raton, FL: Chapman and Hall/CRC, 2004. 364 p.

272. Krause P., Clark D. Representing Unsertain Knowledge. London: Kluwer Acad. Publ., 1993. 278 p.

273. Kreinovich V. A review of "Uncertain reasoning" by G. Shafer and J. Pearl (eds.) // SIGART Bulletin. 1992. Vol. 3, N. 4. P. 23-27.

274. Kreinovich V., Ferson S. A new Cauchy-based black-box technique for uncertainty in risk analysis // Reliable Engineering and System Safety. 2004. Vol. 85, N. 1-3. P. 267-279.

275. Kreinovich V., Joslyn C. Convergence properties of an interval probabilistic approach to system reliability estimation // International Journal of General Systems. 2005. Vol. 34, N. 4. P. 465-482.

276. Kreinovich V., Longpre L., Patangay P., Ferson S., Ginzburg L. Outlier detection under interval uncertainty: algorithmic solvability and computational complexity // Reliable Computing. 2005. Vol. 11, N. 1. P. 59-76.

277. Kreinovich V., Nguen H. Т., Mukaidono N. Probability of Implication, Logical Version of Bayes Theorem, and Fuzzy Logic Operations // Proceedings of the 2002 IEEE International Conference on Fuzzy Systems. Hawaii, 2002. P. 530-535.

278. Kruse R., Schwecke E., Klawonn F. On a Tool for Reasoning with Mass Distributions // Proc. of 12th International Joint Conference on Artificial Intelligence. Sydney: Morgan Kauf-mann Publ., 1991. P. 1190-1195.

279. Kyburg H. E. Bayesian and Non-Bayesian Evidentional Updating // Artificial Intelligence. 1987. Vol. 31. P. 271-293.

280. Kyburg H. E. Representing Knowledge and Evidence for Decision // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 30-40.

281. Kyburg H. E., Teng С. M. Uncertain inference. Cambridge: Cambridge University Press, 2001. 298 p.

282. Kyburg H. E. J. Epistimological Relevance and Statistical Knowledge // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 4). 1990. Vol. 9. P. 159168.

283. Lam F. С., Yeap W. К. Bayesian Updating: on the Interpretation of the Exhaustive and Mutually Exclusive Assumptions // Artificial Intelligence. 1992. Vol. 53. P. 245-254.

284. Larranaga P., Kuijpers G., Poza M., Murga R. Decomposing Bayesian networks: tri-angulation of the moral graph with genetic algorithms // Statistics and Computing. 1997. Vol. 7, N. 1. P. 19-34.

285. Lemmer I. F. Confidence Factors, Imprecision and the Dempster-Shafer's Theory of Evidence // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 117-127.

286. Little R. J. A., Rubin D. B. Statistical Analysis with Missing Data. 2nd ed. N.Y.: Wiley, 2002. 408 p.

287. Liu W. The Incidence Propagation Method // Proceedings of 26th IEEE International Symposium on Multiple-Valued Logic (ISMVL 1996), Santiago de Compostela, Spain. 1996. P. 124-129.

288. Liu W., Bundy A. Constructing probabilistic ATMS Using Extended Incidence Calculus // International Journal of Approximate Reasoning. 1996. Vol. 15. P. 145-182.

289. Liu W., McBryan D., Bundy A. A Comprehensive Comparison between Generalized Incidence Calculus and Dempster Shafer Theory of Evidence / / International Journal of Man-Machine Studies. 1994. Vol. 42. P. 462-491.

290. Liu W., McBryan D., Bundy A. The Method of Assigning Incidences // Applied Intelligence. 1998. Vol. 9, N. 2. P. 139-161.

291. Loui R. P. Interval-Based Decisions for Reasoning Systems // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 459-472.

292. Lui X.-H. Linear Л-paramodulation in Operator Fuzzy Logic // Proc. of 11th International Joint Conference on Artificial Intelligence. Detroit: Morgan Kaufmann Publ., 1989. P. 435440.

293. Lukasiewicz J. Die logische Grundlagen der Wahrscheinlichkeitsrechnung. Cracow, 1913.

294. Lukassen A., Vossen G. A Formal Framework for Independence with Respect to Transactions in the Universal Relation Model // Theoretical Computer Science. 1991. Vol. 82, N. 2. P. 303-327.

295. Mah R. S., Stanley G. M., Downing D. M. Reconciliation and Rectification of Process Flow and Inventory Data // Ind. Eng. Chem., Process Des. Dev. 1976. Vol. 15, N. 1. P. 175183.

296. Martin-Clouaire R. Efficient Deduction in Fuzzy Logic // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 123-136.

297. McLean R. G., Bundy A., Liu W. Assignment methods for incidence calculus // International Journal of Approximate Reasoning. 1995. Vol. 12, N. 1. P. 21-41.

298. Megiddo N. Towards a genuinely polynomial algorithm for linear programming // SIAM Journal of Computing. 1983. Vol. 12. P. 347-353.

299. Minkowski H. Geometrie der Zahlen (Erste Lieferung). Teubner, Leipzig, 1896.

300. Narin'yam A. S. Subdefinite Models: A Big Jump in Knowledge Processing Technology // Proc. of East-West Conference on Artificial Intelligence-93. Moscow, 1993. P. 227-231.

301. Neapolitan R. E. Learning Bayesian Networks. Pearson Prentice Hall, 2004.

302. Nemhauser G. L., Wolsey L. A. Integer and Combinatorial Optimization. N.Y.: Wiley, 1999.

303. Neufeld E., Horton J. D. Conditioning on Disjunctive Knowledge // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 5). 1990. Vol. 10. P. 117-127.

304. Nguen H. Т., Walker E. W. A First Course in Fuzzy Logic. N.Y., London, Washington: Chapman & Hall/CRC, 2000. 373 p.

305. Nilsson N. J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 28. P. 71-87.

306. Nilsson N. J. Logic and Artificial Intelligence // Artificial Intelligence. 1991. Vol. 47. P. 3156.

307. Nilsson N. J. Probabilistic Logic Revisited // Artificial Intelligence. 1993. Vol. 59. P. 39-42.

308. Norwich А. М., Тйгк§еп I. В. A model for the measurement of membership and the consequences of its empirical implementation // Fuzzy Sets and Systems. 1984. Vol. 12, N. 1. P. 1-25.i

309. Oblow E. M, O-Theory: a Probabilistic Alternative to Fuzzy Set Theory // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 111-119.

310. Oblow E. M. Probabilistic Reasoning Using Graphs // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 201-202.

311. Orponen P., Floreen P., Myllymaki P., Tirri H. A Neural Implementation of Bayesian Reasoning // STeP-90 / Ed. by M. Djupsund, P. Salonen, M. Syrjanen. Uupsalu, 1990. P. 277-282.

312. Orshansky M., Wang W.-S., Ceberio M., Xiang G. Interval-based robust statistical techniques for non-negative convex functions, with application to timing analysis of computer chips // Proceedings of the ACM Symposium on Applied Computing SAC'06. 2006.

313. Ovsyannikov D. A. Control Problem under Uncertain Condition // International Conference on Interval and Computer-Algebraic Methods in Science and Engineering. Abstracts. S.-Petersburg, 1994. P. 192.

314. Parsons S. Current Approaches to Handling Imperfect Information in Data and Knowledge Bases // IEEE Transactions on Knowledge and Data Engeneering. 1996. Vol. 8, N. 3. P. 353372.

315. Parsons S. Qualitative methods for reasoning under uncertainty. Cambridge, MS: The MIT Press, 2001. 506 p.

316. Patterson D. W. Introduction to Artificial Intelligence and Expert Systems. N.Y.: Prentice-Hall International, 1990. 450 p.

317. Pearl J. How to Do with Probabilities what People Say You Can't // Artificial Intelligence Applications. / Ed. by C. R. Weisbin. Amstredam: IEEE, 1985. P. 6-12.

318. Pearl J. A Constraint-Propagation Approach to Probabilistic Reasoning // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 357-369.

319. Pearl J. Fusion, Propagation, and Structuring in Belief Networks // Artificial Intelligence. 1986. Vol. 29. P. 241-288.

320. Pearl J. On Evidentional Reasoning in Hierarchy of Hypotheses // Artificial Intelligence. 1986. Vol. 28. P. 9-15.

321. Pearl J. Distributed Revision of Composite Beliefs // Artificial Intelligence. 1987. Vol. 33. P. 173-215.

322. Pearl J. Distributed Revision of Composite Beliefs // Artificial Intelligence. 1987. Vol. 35. R 259-271.

323. Pearl J. Probabilistic reasoning using graphs // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Springer-Verlag, 1987. P. 201-202.

324. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. N.Y.: Morgan Kaufman Publ., 1991. 552 p.

325. Pearl J. How to do with probabilities what'people say you can't // Artificial Intelligence in Medicine / Ed. by S. Quaglini, P. Barahona, S. Andreassen. LNAI2101, 2001. P. 283-292.

326. Pearl J., Dechter R. Directed Constraint Network: a Relational Network for Causal Modelling // Proc. of 12th International Joint Conference on Artificial Intelligence. Sydney: Morgan Kaufmann Publ., 1991. P. 1164^1170.

327. Pearl J., Geiger D. On the Logic of Causal Models // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 4). 1990. Vol. 9. P. 3-14.

328. Pearl J., Goldszmidt M. Deciding Consistency of Databases Containing Defeasible and Strict Information // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 5). 1990. Vol. 10. P. 87-98.

329. Pearl J., Verma T. Causal Networks: Semantics and Expressiveness // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 4). 1990. Vol. 9. P. 69-77.

330. Peot M. A., Shachter R. D. Fusion and Propagation with Multiple Observations in Belief Networks // Artificial Intelligence. 1991. Vol. 48. P. 299-318.

331. Picques J.-D. A Framework for Managing Uncertainty in Embedded Expert Systems // Proc. of the IEEE/ACM International Conference on Developing and Manging System Programs. Sep., 30 Oct., 2. Washington, 1991. P. 59-67.

332. Prade H. A Computational Approach to Approximate and Plausible Reasoning with Applications to Expert Systems // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1985. Vol. PAMI-7, N. 3. P. 260-283.

333. Prade H., Testemale C. Application of Possibility and Necessity Measures to Documentary Information Retrieval // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 265-274.

334. Quinlan J. R. Inferno: a cautious approach to uncertain inference // Computer J. 1983. Vol. 26, N. 3. P. 255-268.

335. Ramsey F. P. Truth and Probability // The Foundations of Mathematics and other Logical Essays. London: Routledge and Kegan Paul, 1931. P. 156-198.

336. Romer С., Kandel A. Applicability Analysis of Fuzzy Inference by means of Generalized Dempster-Shafer Theory // IEEE Transactions on Fuzzy Systems. 1995. Vol. 3, N. 4. P. 448453.

337. Ruspim E. H. Approximate Inference and Interval Probabilities // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 85-94.

338. Sage A, P. On the Management of Information Imprecision in Knowledge-Based Systems // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 3-29.

339. Schrijver A. Theory of Linear and Integer Programming. N.Y.: Wiley, 1999.

340. Schum D. A., Matrin A. W. Formal and empirical research on cascaded inference in jurisprudence // Law and Society Rev. 1982. P. 105-157.

341. Shafer G. A mathematical theory of evidence. Princeton: Princeton University Press, 1976. 78 p.

342. Shafer G. Hierarchical Evidence // Artificial Intelligence Applications / Ed. by C. R. Weis-bin. Amsterdam: IEEE, 1985. P. 16-21.

343. Shafer G. Probability Judgement in Artificial Intelligence // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 128-135.

344. Shamir R. Advanced topics in graph algorithms: Tech. rep.: Tel-Aviv University, 1994'.

345. Shoenfield J. R. Mathematical Logic. Addison-Wesley, Reading, Mass., 1967.

346. Shoham Y., Moses J. Belief as Defeasible Knowledge // Proc. of 11th International Joint Conference on Artificial Intelligence. Detroit: Morgan Kaufmann Publ., 1989. P. 1168-1173.

347. Sittig D. G., Cheung K.-H., Berman L. Fuzzy Classification of Heart Rate Trends and Artifacts // Proc. of 5th Annual IEEE Symposium on Computer-Based Medical Systems. Washington, 1992. P. 510-517.

348. Smets P. Belief Functions versus Probability Functions // Uncertainty and Intelligent Systems / Ed. by B. Bouchon, L. Saitfa, R. R. Yager. Berlin: Springer-Verlag, 1988. P. 17-24.

349. Smets P., Kennes R. The Transferable Belief Model // Artificial Intelligence. 1994. Vol. 66. P. 191-234.

350. Smith С. A. B. Consistency in statistical inference and decision // Journal of the Royal Statistical Society, Series B. 1961. Vol. 23. P. 1-37.

351. Smith С. A. B. Personal probability and statistical analysis // Journal of the Royal Statistical Society, Series A. 1965. Vol. 128. P. 469-499.

352. Sombe L. Raisonnements sur des informations incompletes en Intelligence Artificielle. Toulouse, 1989. 221 p.

353. Spiegelhalter D. J. Probabilistic Reasoning in Predictive Expert Systems // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 47-67.

354. Stepanou H. E., Sage A. P. Perspectives on Imperfect Information Processing // IEEE Transactions on Systems, Man, and Cybernetics. 1987. Vol. SMC-17, N. 5. P. 780-798.

355. Steve G. Probabilistic Inferential Engines in Expert Systems: How Should the Strength of Rules be Expressed? // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 180-188.

356. Studeny M., Bouckaert R. On chain graph models for description of conditional independence structures // The Annals of Statistics. 1998. Vol. 26, N. 4. P. 1434-1495.

357. Suermondt H. I., Cooper G. F. Initialisation for the Method of Conditioning in Bayesian Belief Networks // Artificial Intelligence. 1991. Vol. 50. P. 83-94.

358. Tanaka K., Kobayashi S., Sakanoue T. Uncertainty Management in Object-Oriented Database Systems // Database and Expert Systems Applications / Ed. by D. Karagiannis. Berlin: Springer-Verlag, 1993. P. 251-256.

359. Tarjan R., Yannakakis M. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduct acyclic hypergraphs // SIAM Journal on Computing. 1984. Vol. 13. P. 566—579.

360. Tarski A. A Decision Method for Elementary Algebra and Geometry. Univ. of California Press, 2nd edition, 1951.

361. Tarushkm V. T. Fuzzy Logic and Medical Diagnostic // International Conference on Interval and Computer-Algebraic Methods in Science and Engineering. Abstracts. S.-Petersburg, 1994. P. 235.

362. Tessem B. Extending the A/R algorithm for interval probability propagation: Tech. Rep. 42: University of Bergen, Norway, Department of Informatics, 1992.

363. Tessem B. Interval probability propagation: Tech. Rep. 39: University of Bergen, Norway, Department of Informatics, 1992.

364. Tessem B. Interval probability propagation // International Journal of Approximate Reasoning. 1992. Vol. 7, N. 3/4. P. 95-120.

365. Turkmen I. B. Measurement of membership functions and their acquisition // Fuzzy Sets and Systems. 1991. Vol. 50, N. 1. P. 5-38.

366. Voorbraak F. On the Justification of Dempster's Rule of Combination // Artificial Intelligence. 1991. Vol. 48. P. 171-179.

367. Walley P. Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London, 1991.

368. Walley P. Inferences from multinomial data: learning about a bag of marbles // Journal of the Royal Statistical Society, Series B. 1996. Vol. 58. P. 3-57.

369. Wang P. A Defect in Dempster-Shafer Theory // Proceedings of the Tenth Conference of Uncertainty in Artificial Intelligence / Ed. by R. L. d. Mantaras, D. Poole. Seattle, 1994.

370. Wang Z. Some Recent Advances on the Possibility Measure Theory // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 172-175.

371. Weiss Y. Correctness of local probability propagation in graphical models with loops // Neural Computation. 2000. Vol. 12. P. 1-41.

372. Wellman M. P. Fundamental Concepts of Qualitative Probabilistic Networks // Artificial Intelligence. 1990. Vol. 44. P. 257-303.

373. Whalen T. Interval probabilities induced by decision problems // Advances in the Dempster-Shafer Theory of Evidence / Ed. by R. R. Yager, J. Kacprzyk, M. Pedrizzi. 1994. P. 353-374.

374. Whalen Т., Bronn C. Hurwicz and regret criteria extended to decisions with ordinal probabilities // Proc. of 1990 North Amer. Fuzzy Inform. Proc. Soc. Conference. 1990. P. 219-222.

375. Wilkins D. C., Ma Y. The Refinement of Probabilistic Rule Sets // Artificial Intelligence. 1994. Vol. 70. P. 1-32.

376. Winkler R. L. The assessment of prior distributions in Bayesian analysis // J. Amer. Statist. Assoc. 1967. Vol. 62. P. 776-800.

377. Wise В. P., Henrion M. A Framework for Comparing Uncertain Inference Systems to Probability // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 69-83.

378. Xiang Y., Beddoes M. P., Poole D. Can Uncertainty Management be Realized in a Finite Totally Ordered Probability Algebra // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence, 5). 1990. Vol. 10. P. 41-57.

379. Yager R. R. Possibilistic Qualification and Default Rules // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Berlin: Springer-Verlag, 1987. P. 41-57.

380. Yannakakis M. Computing the minimum fill-in is NP-complete // SIAM Journal of Algorithms and Discrete Mathematics. 1981. Vol. 2. P. 77-79.

381. Yen J. Generalizing Term Subsumption Languages to Fuzzy Logic // Proc. of 12th International Joint Conference on Artificial Intelligence. Sydney: Morgan Kaufmann Publ., 1991. P. 472-477.

382. Young R. E., Ress D. A. FuzCon: A Fuzzy Constraint Application Development Environment // SCM'98. Сборник докладов. T.l. СПб., 1998. P. 12-25.

383. Zadeh L. A. Probabilistic Reasoning in Predictive Expert Systems // Machine Intelligence & Pattern Recognition (Uncertainty in Artificial Intelligence). 1986. Vol. 4. P. 103-116.

384. Zellner A. An Introduction to Bayesian Inference in Econometrics. Wiley, N. Y., 1971.

385. Zimmermann H. H., Zysno P. Latent connectives in human decision making // Fuzzy Sets and Systems. 1980. Vol. 4. P. 37-51.

386. Нередуцируемая DS-структура. 41

387. Эквивалентная вероятностная структура. 4413. .х — означивание и оценка истинности. 50

388. Обоснование исчисления инциденций. 57

389. Инциденции с неопределенностью. 59

390. Аргументное место как связанная переменная. 62

391. Набор противоречивых высказываний. 72

392. Пропущенные наблюдения. 78

393. Оценка истинности импликации. 80110. БСД с двумя узлами . 104

394. АБС над двумя атомами. 105112. БСД с тремя узлами. 106

395. Циклические паттерны в байесовских сетях . 106

396. Вычисление совместных вероятностей в БСД. 123

397. Взаимодействие свидетельства и исходов. 126

398. Элиминация переменной в БСД. 130

399. Пропагация в БСД при наличии свидетельств . 153

400. Назначение скалярных оценок вероятностей. 213

401. Назначение интервальных оценок вероятностей. 21443. Матрица 14. 227

402. Множество ограничений IR(2) . 234

403. Множество ограничений £(3). 235

404. Modus ponens и априорный вывод. 245

405. Вероятности конъюнктов и логических связок. 245

406. Оценки вероятности в РФЗ. 24949. Противоречивость. 249410. Уточнение оценок. 250

407. Качественные оценки.'. 251

408. Количественные оценки. 251

409. Количественные и качественные оценки. 251

410. Скалярная оценка вероятности . 252

411. Последовательное переозначивание. 255

412. Переозначивание трех атомов. 256

413. Состав множеств ограничений U{z) eW'(£) . 264

414. Чувствительность 6'(е) оценки p(xi VX2VX3). 266419. -Пример обучающей выборки. 277

415. Апостериорный вывод на ФЗ второго порядка. 297

416. Апостериорный вывод на ФЗ третьего порядка. 298

417. Апостериорный вывод: кортеж свидетельств . 300

418. Апостериорный вывод в ФЗ со скалярными оценками . 302

419. Распространение свидетельства. 309

420. Ограничения непротиворечивостей. 342

421. Ограничения непротиворечивостей 2. 345

422. Экстернальная и интернальная непротиворечивости. 352

423. Различие глобальной и интернальной степеней непротиворечивости353

424. АБС, непротиворечивая лишь экстернально. 35356. Вторичная ЗЛП. 356

425. Различная точность оценок. 359

426. Оценка посредством продолжения. 359

427. Оценка через подформулы. 360510. Тривиальная оценка. 361

428. Оценки через погружение в ФЗ. 361

429. Композиция распределений СБП. 365

430. Независимость при пустом пересечении СБП. 365

431. Структуры двух АБС из БСД с рис. 2.1.416

432. БСД-цикл из трех вершин.455

433. Противоречивый БСД-цикл с бинарными оценками.462

434. Противоречивый БСД-цикл с небинарными оценками . 463

435. А.1. Байесовский вывод. 589

436. А.2. Свертка байесовского вывода. 590

437. А.З. Проявление условной независимости. 591

438. А.4. Зависимость гипотез. 591

439. А.5. Зависимость свидетельств. 594

440. А.6. Пример произведения Кронекера. 599

441. А.7. Внешняя и внутренняя меры. 6051. Список иллюстраций

442. Функции доверия и весовые функции. 40

443. Фокальные элементы ТВН. 4513. t-нормы. 5614. t-конормы. 57

444. Исчисление инциденций с неопределенностью. 60

445. Вероятности п-го типа . 8417. Примеры ССФЗ. 95

446. Простейшие байесовские сети. 105

447. Байесовские сети доверия с тремя узлами. 105

448. Циклические паттерны в байесовских сетях. 105

449. Примеры марковских сетей на решетках и графе. 108

450. Пример базового графа байесовской сети доверия . 115

451. Виды связей, используемых для d-разделимости. 117

452. Пример байесовской сети доверия. 121

453. Моральный граф примера из рис. 2.1. 129

454. Моральный граф после элиминирования переменной и. 131

455. Идеальная элиминирующая последовательность. 133

456. Несоседние симплициальные вершины. 135

457. Граф, не являющийся триангулярным. 135

458. Дерево смежности для морального графа из рис. 2.4. 137

459. Дерево сочленений для морального графа из рис. 2.4. 138

460. Идеальная нумерация вершин морального графа. 139

461. Построение дерева сочленений. 141

462. Поиск идеальной нумерации в триангулярном графе. 142

463. Построение дерева смежности. 142

464. Простейший алгоритм триангуляции . 143

465. Неидеальная работа алгоритма триангуляции. 143

466. Первые два шага алгоритма первичной пропагации. 148218. Схема пропагации. 153

467. Схема вычислений при пропагации. 154

468. Примеры к понятию графа и дерева смежности. 18341. Матрица Ii. 22742. Матрица 12. 22843. Матрица 13. 22944. Матрица 14. 22945. Матрица 15. 23046. Матрица 16. 23047. Матрица 17. 23148. Произведение идеалов. 232

469. Алгоритм поддержания непротиворечивости ФЗ. 240

470. Алгоритм переозначивания атомов. Скалярный случай. 258

471. Переозначивания атомов. Интервальный случай. 259

472. График б'(£) к примеру 4.18. 267

473. Апостериорный вывод. Скалярный случай. 297

474. Обработка детерминированных и стохастических свидетельств.303

475. Пропагация стохастического свидетельства. 304

476. Алгоритм пропагации свидетельства ФЗ АБС. 316

477. Пропагация недетерминированного свидетельства 1'. 318

478. Пропагация недетерминированного свидетельства 2. 319

479. Экстернальная и интернальная непротиворечивости. 342

480. Непротиворечивость двух ФЗ с «точечным» пересечением. 343

481. Непротиворечивость ФЗ с меньшим под-ФЗ в пересечении. 343

482. Оценки с различными требованиями к согласованности.349

483. Интернальная и глобальная непротиворечивости не совпадают.353

484. Алгоритм. Интернальная непротиворечивость. 355

485. Диаграмма Хассе АБС N3(2)3. 357

486. Диаграмма Хассе АБС N222. 357

487. Схема вывода со вторичной ЗЛП. 357

488. Два порядка продолжения вероятности. 368511. Поиск распределения. 369

489. Распространение свидетельства: общий случай. 391513. Цепь из четырех ФЗ. 393

490. Разделенная цепь из четырех ФЗ. 394

491. Дерево апостериорных вероятностей. 396

492. Линейное дерево апостериорных'вероятностей. 399

493. Распространение апостериорных вероятностей.400

494. Апостериорный вывод в АБС из ФЗ порядка 2. 401

495. Апостериорный вывод в АБС из ФЗ порядка 3.402

496. Распространение влияния свидетельства в случае скалярных оценок вероятностей. 405

497. Распространение свидетельства в двух ФЗ, погруженных в третий. 407

498. АБС (из БСД с рис. 2.1) без циклов. 416

499. АБС (из БСД с рис. 2.1) с циклами.41761. Циклы в АБС. 423

500. Выделение цепи смежности из цикла в АБС.432

501. Примеры направленных циклов в БСД. 436

502. Фазы алгоритма первичной пропагации в БСД-цикле.441

503. Цепь, возникающая при размыкании БСД-цикла. 453

504. БСД-цикл из трех узлов. 456

505. Преобразование БСД-цикла в цепь ФЗ АБС. 459

506. Примеры преобразования БСД-цикла в цепь ФЗ АБС. 459

507. БСД с направленным циклом.472

508. Потомки БСД-цикла со скалярной оценкой вероятности означиваний СБЭ.474

509. Потомки БСД-цикла с интервальной оценкой вероятности означиваний СБЭ. 474

510. Структура пакетов системы.486

511. Представление АБС в базе данных.491

512. Представление графа смежности и его подвидов в БД.493

513. Представление свидетельств в базе данных. 494

514. Представление сессии и ее результатов в случае проверки и поддержания непротиворечивости. 496

515. Представление сессии и ее результатов в случае апостериорного вывода. 498

516. Представление алфавитов в базе данных. 498

517. Интерфейсы чтения и записи оценок вероятностей в ФЗ. 500

518. Иерархия интерфейсов пакета algbn.data.local. 502

519. Различные компоновки для визуализации графа смежности.509

520. Иерархия интерфейсов проверки локальной непротиворечивости. 509

521. Иерархия классов локального апостериорного вывода. 516

522. Иерархия классов глобального апостериорного вывода. 518

523. А.1. Пример к понятию графа. 596

524. А.2. Основные понятия теории графов. 598

525. А.З. Примеры подграфов и не подграфов. 599

526. A.4. Внутренняя и внешняя меры, пример А.7. 605

527. Б.1. Два пересекающихся ФЗ второго порядка. 610

528. Б.2. Пересечение ФЗ размерностей 2иЗ. 610

529. Б.З. Пересечение ФЗ размерностей ЗиЗ. 610

530. Б.4. БСД из двух узлов.*. 618

531. Б.5. БСД из двух узлов с предками. 620

532. Б.б. АБС и БСД из двух ФЗ на трех переменных. 622

533. Б.7. Линейные цепи ФЗ в АБС и БСД. 624

534. B.1. Копия акта о применении результатов диссертационного исследованияв учебном процессе от СПбГУ ИТМО. 633

535. В.2. Копия акта об использовании материалов и результатов исследованийот СПбГУ. 634

536. В.З. Копия акта о внедрении результатов научных исследований от ОАО1. СПИК СЗМА. 635

537. В.4. Копия свидетельства № 2009613802. 637

538. В.5. Копия уведомления № 2009613802. 638

539. В.6. Копия свидетельства № 2009613803. 639

540. В.7. Копия уведомления № 2009613803. 640

541. В.8. , Копия свидетельства № 2009613804. 641

542. В.9. Копия уведомления № 2009613804. 642

543. В.10. Копия свидетельства № 11607. 644

544. В.11. Копия извещения № 11607. 645

545. В Л 2. Копия лицевой стороны ИКАП № 11607. 646

546. В.13. Копия оборотной стороны ИКАП № 11607. 647

547. В. 14. Копия свидетельства № 12235. 648

548. В. 15. Копия извещения № 12235. 649

549. В.16. Копия лицевой стороны ИКАП № 12235. 650

550. В.17. Копия оборотной стороны ИКАП № 12235. 651

551. В.18. Копия свидетельства № 12001. 652

552. В.19. Копия извещения № 12001. 653

553. В.20. Копия лицевой стороны ИКАП № 12001. 654

554. В.21. Копия оборотной стороны ИКАП № 12001. 655

555. В.22. Копия свидетельства № 12174. 656

556. В.23. Копия извещения № 12174. 657

557. В.24. Копия лицевой стороны ИКАП № 12174. 658

558. В.25. Копия оборотной стороны ИКАП № 12174. 659

559. В.26. Копия свидетельства № 12175. 660

560. В.27. Копия извещения № 12175. 661

561. В.28. Копия лицевой стороны ИКАП № 12175. 662

562. В.29. Копия оборотной стороны ИКАП № 12175. 663

563. В.30. Копия свидетельства № 12234. 664

564. В.31. Копия извещения № 12234. 665

565. В.32. Копия лицевой стороны ИКАП № 12234. 666

566. В.ЗЗ. Копия оборотной стороны ИКАП № 12234. 667

567. Г.1. Общая схема базы данных. 669

568. Г.2. Фрагмент схемы БД без унификации видов АБС и свидетельств.670